2020 KAKAO BLIND RECRUITMENT - 외벽 점검(c++)

Greedy +  완탐 문제이다.

투입될 친구의 수를 정하고 시작할 위치를 정한다.

그리고 시작할 위치에서 투입될 친구 수만큼을 투입하면 모든 취약 지점을 커버할 수 있는 지를 파악한다.

 

중요한 점은!

원형의 외벽이기 때문에 취약지점에 (weak.size()-1)만큼 원소를 더 넣어준다.

ex) [1, 5, 6, 10] -> [1, 5, 6, 10, 13, 17, 18]이 된다.

그래야 이후에 계산을 할 때에 편하게 할 수 있다.

 

그리고 투입될 친구의 수를 1~dist_len까지 작은 수 부터 투입을 했기 때문에

그 수에서 바로 모든 취약지점이 커버된다면 바로 return i를 해주면 된다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = -1; // 모두 점검할 수 없으면 -1
    
    int weak_len = weak.size();
    int dist_len = dist.size();
    
    sort(dist.begin(), dist.end());
    for(int i=0; i<weak_len-1; i++){
        weak.push_back(weak[i]+n);
    }
    
    for(int i=1; i<=dist_len; i++){ // 투입될 친구 수
        for(int j=0; j<weak_len; j++){ // 시작할 위치
            
            vector<int> temp; // 외벽점검에 투입될 친구
            for(int k=dist_len-i; k<dist_len; k++){
                temp.push_back(dist[k]);
            }
            
            do {
                int idx = 0;
                for(int k=0; k<temp.size(); k++){
                    int End = weak[j+idx]+temp[k];
                    while(weak[j+idx+1]<=End){
                        idx++;
                    }
                    idx++; // 다음 취약 지점으로 이동
                }
                if(idx>=weak_len){
                    return i;
                }
            } while(next_permutation(temp.begin(), temp.end()));
        }
    }
    
    return answer;
}