[lv3] 외벽 점검

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

 

구현 + 순열 문제다.

풀이법은 [모든 weak 경우]에 [모든 dist 경우]를 비교해서, 각 탐색이 weak point를 다 덮을 수 있는지 판단하면 된다.

 

 

실수한 부분

 

맨 처음에 그리디 문제인가 고민하다 아니라고 생각했다. (확정은 못지었다.)

이후 완전탐색 하기로 했지만, 코드에 사용한 로직의 복잡도를 O(15! * 8!)로 착각해서 적용하기까지 오래걸렸다.

 

=> dist를 뽑는 경우의 수는 순열이므로 8!인데 반해,

=> weak는 순서가 변하지 않으므로 15!이 아닌 15였다.

 

+ 15!는 약 1조3천억 이었다.

 

 

---

 

풀이법

 

 

1. weak 경우의 수 구하기

 

각 취약지점 배정 순서를 달리하기 위해, 다음과 같이 배열을 1칸씩 이동시키며 기록한다.

[1,5,6,10] -> [5,6,10,1] -> [6,10,1,5] -> ....

 

이는 취약지점이 움직인다기 보다, 취약지점은 고정인 채로 사람이 배정될 시작점을 바꾸는 동작에 가깝다.

 

다만, 나는 지점이 아니라 지점간의 거리차를 기록했다.

이를 deque에 저장하고 toArray()하여 사용했다.

 

 

2. dist 경우의 수 구하기

순열 + 재귀로 구해서 list에 저장했다.

 

1번과 합치면, 모든 취약지점을 시작점으로 하는 모든 사람의 순서를 탐색할 수 있게된다 (= 완전탐색)

 

 

3. 유효성 판단

 

3-1. 배치 방법 (약간의 그리디)
- 취약 지점에만 사람을 배치해도 된다. == 지점 사이에 배치해야만 최적인 경우는 없다.
- 한 명이 커버 가능한 지점엔 다른 인원을 두지 않아도 된다.

 

3-2. 구현

한 지점에 사람을 배정한다.

이후, 사람의 dist에 다음 지점이 포함되는 동안 모두 커버시킨다.

포함되지 않는다면, 다음 사람을 배정한다.

 

탐색을 마치고 모든 영역을 커버했다면 정답을 갱신한다.

import java.util.*;

class Solution {
    Deque<Integer> diff = new ArrayDeque<>();
    List<int[]> permuList = new ArrayList<>();
    boolean[] picked;
    int[] pick, dist;
    int W, D, answer = Integer.MAX_VALUE;

    // O(15 * 8!)
    void solve(int dep) {

        if(dep == W)
            return;

        // weak 경우의 수 <= 15
        int[] weak = diff.stream().mapToInt(Integer::valueOf).toArray();
        diff.offerLast(diff.pollFirst());

        // dist 경우의 수 <= 8!
        for(int i=0; i<permuList.size(); i++) {
            int[] dst = permuList.get(i);

            int wIdx = 0;
            int dIdx = 0;
            int people = 0;

            while(wIdx < W && dIdx < D) {

                // 취약 지점에 한 명 배치
                people++;
                wIdx++;

                // 한 명이 커버 가능한 곳 추가 탐색
                int remainD = dst[dIdx];
                dIdx++;

                while(wIdx < W && remainD >= weak[wIdx]) {
                    remainD -= weak[wIdx];
                    wIdx++;
                }
            }

            // 취약 지점을 모두 커버한 경우
            if(wIdx == W)
                answer = Math.min(answer, people);

        }

        solve(dep + 1);
    }

    public int solution(int n, int[] weak, int[] dist) {
        W = weak.length;
        D = dist.length;
        this.dist = dist;
        picked = new boolean[D];
        pick = new int[D];

        for(int i=0; i<W-1; i++)
            diff.offerLast(weak[i+1] - weak[i]);

        diff.offerLast(n - weak[W-1] + weak[0]);

        permu(0);
        solve(0);

        return answer == Integer.MAX_VALUE? -1 : answer;
    }

    void permu(int dep) {

        if(dep == D) {
            permuList.add(pick.clone());
            return;
        }

        for(int i=0; i<D; i++) {
            if(!picked[i]) {
                picked[i] = true;
                pick[dep] = dist[i];
                permu(dep + 1);
                picked[i] = false;
            }
        }
    }
}