[Algorithm] Programmers :: 외벽 점검

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

프로그래머스

vector<int> weaks, dists;
int targetCount = 0;
int minNum = 0x3f3f3f3f;
 
void DFS(int curWeakIndex, int count, int distIndex, int friends, int n)
{
    if (distIndex == dists.size()) return;
    
    ++count;
    ++friends;
    int remainingDist = dists[distIndex];
 
    while (count != targetCount)
    {
        if (curWeakIndex == targetCount) curWeakIndex = 0;
        int nextIndex = curWeakIndex + 1;
        if (nextIndex == targetCount) nextIndex = 0;
 
        int curNum = weaks[curWeakIndex];
        int nextNum = weaks[nextIndex];
 
        int gap = nextNum < curNum ? nextNum + n - curNum : nextNum - curNum;
 
        if (gap <= remainingDist) // 커버되면
        {
            ++count;
            ++curWeakIndex;
            remainingDist -= gap;
        }
        else break;
    }
 
    if (count == targetCount)
    {
        minNum = min(minNum, friends);
        return;
    }
 
    DFS(curWeakIndex + 1, count, ++distIndex, friends, n);
}
 
int solution(int n, vector<int> weak, vector<int> dist) 
{
    int answer = 0;
 
    sort(dist.begin(), dist.end());
    weaks = weak;
    dists = dist;
 
    targetCount = weak.size();
 
    do
    {
        for (int i = 0; i < weak.size(); ++i)
        {
            DFS(i, 0, 0, 0, n);
        }
 
    } while (next_permutation(dists.begin(), dists.end()));
 
    if (minNum == 0x3f3f3f3f) return -1;
 
    return minNum;
}

완전탐색문제인거를 바로 알아채리지 못해서 많은 시간이 걸린 문제이다..

최소한의 인원을 투입해서 외벽을 고쳐야하는 문제인데, 문제만 봤을때는 시계방향,반시계방향을 전부 검사해야만 할 것 같은 문제다. 

나 또한 그랬고, 그러다보니 코드도 난잡하고 헷갈리기만 했다.

그러다 힌트를 봤는데 완전탐색한다는 가정을 했을때 반시계방향을 검사할필요없이 시계방향으로만 검사해도 된다는 것이다. 어차피 모든 취약지점에 대해서 검사할것이기 때문에, 반시계방향을 검사할 필요가 없는것이다.

 

검사자체는 시계방향으로 한다고 가정하고, 취약지점에 대해서는 순열을 구해서 순차적으로 검사해주면 된다.

처음에 그냥 큰값부터 내림차순으로 하면 된다고 생각했는데, 6,10,12,14 케이스에 대해 틀려서 다른사람 글을 찾아보니 비슷한 케이스가 상당히 많았고, 딱 이 4개의 케이스에 대해 저격테스트케이스를 올려주신분 덕분에 순열을 전부 구해야한다는 걸 깨달았다.

해당문제의 '질문하기'에 들어가서 보면 찾을 수 있으니, 같은 문제를 겪는다면 꼭 찾아보길 바란다.

 

순열을 구하는건 next_permutation을 사용했다. 덕분에 코드가 깔끔해보인다.