2020 Kakao blind 60062 - 외벽점검(완전탐색, 구현)

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

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

- 제한사항에 주어진 배열들 길이가 다 짧아서 바 로 완전탐색 로직을 생각해냈다. 
다만 취약지점을 순회하는 방식을 생각해내기가 좀 어려웠던 문제이다. 

- weak의 길이를 2배로 늘리고 기존 weak.size()+1부터 기존의 값 + n인 값을 넣어주고 이 안에서 weak.size() 개수만큼 취약지점을 순회하게 되면 순회를 종료하는 식으로 로직을 짰다.

- 친구들을 투입하는 순서를 완전탐색으로 모두 넣어본 뒤 그 케이스 중 최소인원을 리턴하면 된다.

- upper_bound를 사용하면 기존 순회했던 위치보다 더 크면서 그 중 제일 작은 값을 쉽게 구할 수 있다.(python의 bisect) 내부는 이분탐색으로 구현되어있음.

**upper_bound: 상한, 큰 수 중 첫 번째 수 리턴, lower_bound: 하한, 크거나 같은 수 중 첫번째 수 리턴

** k의 상한의 위치 - k의 하한의 위치 = 가능한 k의 갯수

#include <algorithm>
#define INF 987654321
using namespace std;

int solution(int n, vector<int> weak, vector<int> dist) {
    int ans = INF;
    int wLen = weak.size();
    int dLen = dist.size();

    weak.resize(wLen * 2);
    for (int i = wLen; i < 2 * wLen; ++i) {
        weak[i] = n + weak[i - wLen];
    }  // [1,5,6,10, 13,17,18,22] 여기서 4개 점검하면 됨

    sort(dist.begin(), dist.end());
    do {  // dist: 1234, 1243, 1324, 1342...
        for (int i = 0; i < wLen; ++i) {
            int s = weak[i], e = weak[i + wLen - 1];
            int cnt = 0;
            for (int j = 0; j < dLen; ++j) {
                s += dist[j];
                ++cnt;
                if (s >= e) {
                    ans = min(ans, cnt);
                    break;
                }

                // s보다 큰 weak[j] 중에 제일 작은값
                int nIdx = upper_bound(weak.begin(), weak.end(), s) - weak.begin();
                s = weak[nIdx];
            }
        }
    } while (next_permutation(dist.begin(), dist.end()));

    return ans == INF ? -1 : ans;
}