Programmers - 외벽점검(C++)

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

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

풀이

외벽을 점검하면서 0->n, n->0의 경우를 이어주기위해 weak를 이어붙임

ex) n=8, weak=[1, 4, 7] -> new_weak=[1, 4, 7, 8(1+n), 11(4+n), 14(7+n)]

 

문제 설명에 모든 경우에 대한 탐색(bruteforce)

   1. 어떤 친구를 배정할 것인지

   2. 취약지점 중 어느 곳을 시작지점를 배정할 것인지

   3. 시계방향 or 시계반대방향 중 어느 방향으로 돌 것인지(문제 풀이에 영향이 없다고 생각하고 시계방향으로만 배정)

 

#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = 987654321;
    int weak_size=weak.size();
    
    for(int i=0;i<weak_size;i++){
        weak.push_back(weak[i]+(n));
    }
    
    do{
        for(int start_pos=0;start_pos<n;start_pos++){//시작 위치 (0~n-1)
            //첫번째 사람을 배정
            int human_idx=0;
            int fix=1;
            int nowHuman_endPos=weak[start_pos]+dist[human_idx];
            
            for(int now=start_pos+1;now<weak.size();now++){//시작위치+1 부터 resize한 weak의 사이즈까지 확인
                if(fix==weak_size){//모든 취약 지점에 대한 배정이 끝남
                    answer=min(answer, human_idx+1);
                    break;
                }
                else if(nowHuman_endPos>=weak[now]){//현재 사람이 이동할 수 있는 거리에 다음 취약지점이 포함
                    fix++;
                }
                else{
                    if(human_idx==dist.size()-1)break;//남은 사람이 없다면 외벽을 전부 점검할 수 없다는 의미로 break하고 다음 조합으로 넘어감
                    //다음 취약지점이 현재 사람의 거리로 도달 할수 없으므로 다음 사람을 배정
                    human_idx++;
                    nowHuman_endPos=weak[now]+dist[human_idx];
                    fix++;
                }
            }
        }
        
    }while(next_permutation(dist.begin(), dist.end()));//누구부터 보낼건지에 대한 조합
    
    answer=(answer==987654321?-1:answer);
    
    return answer;
}