[프로그래머스 lv3] 외벽 점검 풀이

해설

그리디와 완전탐색을 이용하는 문제이다.

 

1) dist 원소의 개수는 8 이하이므로 1명, 2명,... , dist.size()명을 보냈을 경우에 대해 각각 완전탐색을 수행할 수 있다. 이때, i명을 보낸다면 dist[i]가 가장 큰 i명을 보내는 것이 유리하고, 따라서 dist를 내림차순으로 정렬하여 0부터 i-1번 까지의 친구(거리)를 사용하면 된다.

 

2) 보내는 친구 수를 결정한 이후, 각 친구를 어떠한 순서로 외벽에 맵핑할 것인지 결정한다. 친구들의 거리가 담긴 order 배열을 오름차순으로 정렬한 후 next_permutation()을 사용하면 선택한 거리에 대한 모든 순서를 탐색할 수 있다.

 

3) 점검을 보내는 친구 수와 각 친구들의 맵핑 순서가 정해졌을 때, 어떠한 취약점을 시작으로 맵핑할 것인지를 결정한다. 예를 들어, n =12, weak = [1, 5, 6, 10] 일 때, 1을 기준으로 맵핑을 시작한다. 만약 1을 기준으로 맵핑했을 때 모든 취약점을 점검할 수 없다면 다음 시작점을 탐색해야 한다. 이때, weak = [5, 6, 10, 13(12+1)]로 변경하여 5를 시작점으로 맵핑한 결과를 쉽게 구하자.

 

정리하면, 

 

for (선택할 친구 수)

    for (선택한 친구들의 나열)

        for (맵핑의 시작점)

              if (모든 취약점을 점검할 수 있다면) 선택한 친구 수 리턴;

 

과 같이 완전탐색을 진행할 수 있다.

 

모든 취약점을 점검할 수 있을 때 선택한 친구 수를 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(int n, vector<int> weak, vector<int> dist) {
    
    sort(dist.begin(), dist.end(), greater<>());

    for (int i=1; i<=(int)dist.size(); i++) {
        
        vector<int> order;
        for (int j=0; j<i; j++) order.push_back(dist[j]);
        sort(order.begin(), order.end());
        
        do {
            vector<int> W = weak;
            for (int k=0; k<(int)W.size(); k++) {
                
                int idx = 0;
                for (auto d : order) {
                    int st = idx;
                    for (; idx < (int)W.size() && W[idx] <= W[st]+d; idx++) {}
                }
                if (idx >= (int)W.size()) return i;

                W.push_back(W[0]+n);
                W.erase(W.begin());
            }
            
        }
        while (next_permutation(order.begin(), order.end()));
    }
    
    return -1;
}