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

프로그래머스 외벽 점검 [2020 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검

문제 풀이

• 이 문제는 모든 지점에서, 각자 다른 순서로 친구들을 보내는 접근의 완전 탐색으로 해결했습니다.
• 반시계 방향으로 외벽을 따라 점검하는 경우가 있는데, 아래의 그림과 같이 1번 -> 5번 반시계 방향 = 5 -> 1번 시계 방향 탐색이기 때문에 반시계 방향은 고려하지 않습니다.

• 모든 지점으로부터 시계 방향 탐색을 하기 위해 마지막 지점을 제외한 각 지점별로 (지점 + N)의 지점을 추가합니다. (위의 예제에서 N = 12)
• 다음과 같이 13, 17, 18 지점을 추가하게 되면 기존의 모든 지점에서 시계 방향 탐색을 진행할 수 있습니다.
  • 1 -> 10
  • 5 - > 13(1)
  • 6 -> 17(5)
  • 10 -> 18(6)

• 각자 다른 순서로 친구들을 보내기 위해 next_permutation을 사용했습니다.

코드

#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = 1e8;
    int w_size = weak.size();
    
    for(int i=0; i<w_size-1; ++i) {
        weak.push_back(weak[i] + n);
    }
    
    sort(dist.begin(), dist.end()); // next_permutation 사용 위해 정렬
    
    do {
        for(int i=0; i<w_size; ++i) {
            int start = weak[i];
            int end = weak[i+w_size-1];
            
            for(int j=0; j<dist.size(); ++j) {
                start += dist[j]; // 친구 이동
                
                if(start >= end) { // 모든 지점 점검 마쳤을 경우
                    answer = min(answer, j+1);
                    break;
                }
                
                // 외벽 점검을 마치지 않았지만 더이상 이동할 수 없으면 다음 지점으로 이동
                for(int z=i+1; z<i+w_size; ++z) {
                    if(weak[z] > start) {
                        start = weak[z];
                        break;
                    }
                }
            }
        }
    } while(next_permutation(dist.begin(), dist.end()));
    
    if(answer == 1e8) return -1;
    
    return answer;
}

실행 결과