https://programmers.co.kr/learn/courses/30/lessons/60062
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
<풀이>
1. 친구를 어디서 부터 보낼 것인지, 어떤 친구부터 보낼 것인지의 경우를 모두 탐색한다.
2. 가장 적게 사용한 친구의 수를 반환한다.
<해법>
1. 친구를 어디서 부터 보낼 것인지
=> 위의 조건에서 친구는 시계방향, 반시계방향 모두 움직일 수 있다고 합니다. 하지만 결국 친구의 수를 가장 적게 사용하려면, 똑같은 방향으로 친구가 탐색하지 못한 다음 취약지점부터 다른 친구를 보내주어야 합니다.
이렇게 되면, 원형으로 나와있는 취약지점이 직선의 경우로 바뀌게 됩니다.
예제 1을 예로들면, (1 5 6 10), (5 6 10 1), (6 10 1 5), (10 1 5 6) 따라서 4가지 경우만 탐색하면 됩니다.
또한, 위의 4가지 경우를 쉽게 탐색하기 위해 맨 앞의 숫자가 뒤로 가면서 숫자 n을 더해주면 직선의 경우가 됩니다.
예제 1을 예로들면, (1 5 6 10), (5 6 10 13), (6 10 13 17), (10 13 17 18) 가 됩니다.
2. 어떤 친구부터 보낼 것인지
=> 친구들이 갈 수 있는 거리가 모두 다르고, 취약 지점마다의 거리가 어떻게 될지 모르니 모든 가짓수를 다 해보아야합니다. 따라서 next_permutation을 사용하였습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<int> weak, vector<int> dist) {
int answer = -1;
//next_permutation을 사용하기 위한 정렬
sort(dist.begin(), dist.end());
//원형탐색 weak.size()만큼 반복
for (int i = 0; i < weak.size(); i++) {
//취약지점 순환
int tmp = weak[0] + n;
for (int j = 1; j < weak.size(); j++) {
weak[j - 1] = weak[j];
}
weak[weak.size() - 1] = tmp;
//친구들 배치
do {
//w : 취약지점 index, d : 친구들 index
int w = 0;
int d = 0;
//친구 한명이 갈 수 있는 취약지점 까지 모두 탐색
for (d = 0; d < dist.size(); d++) {
int fin = weak[w] + dist[d];
while (fin >= weak[w]) {
w++;
if (w == weak.size()) {
break;
}
}
if (w == weak.size()) {
break;
}
}
//모든 취약지점이 탐색 되었다면, 가장 적게 친구를 사용한 결과 저장
if (w == weak.size()) {
if (answer == -1 || d + 1 < answer) {
answer = d + 1;
}
}
} while (next_permutation(dist.begin(), dist.end()));
}
return answer;
}
|
백트래킹에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글
| [C++] 프로그래머스 - 튜플 (0) | 2020.05.07 |
|---|---|
| [C++] 프로그래머스 - 크레인 인형뽑기 게임 (0) | 2020.05.07 |
| [C++] 프로그래머스 - 기둥과 보 설치 (0) | 2020.05.07 |
| [C++] 프로그래머스 - 블록 이동하기 (0) | 2020.05.07 |
| [C++] 프로그래머스 - 자물쇠와 열쇠 (0) | 2020.05.07 |
