[C++] 프로그래머스 - 외벽 점검

https://programmers.co.kr/learn/courses/30/lessons/60062

프로그래머스

<풀이>

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을 사용하였습니다.

#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;
}

 

백트래킹에 대해 알아볼 수 있는 문제였습니다.