[2020 KAKAO BLIND RECRUITMENT] 외벽 점검 (문제접근법, 해설 이해하기)

## 접근

---

1. 시작점을 잡고, 순열을 통해서 모든 외벽의 취약 지점들을 커버할 수 있는지 확인해야 한다. 함수는 필요한 인원수를 반환하는 것으로 정의한다.

 

 

 

2. 외벽은 원의 형태를 이루고 있으므로, 이동할 수 있는 거리는 시계 방향만 고려하면 된다.(반시계로 된다면 시계로도 가능) 이동할 수 있는 거리가, 외벽의 길이를 넘어가면 검사해야 하는 외벽들의 위치에 외벽의 길이만큼 더해줘야 한다.

 

 

 

 

 

## 해설코드

---

class Solution {    
    int[] w;
    int[] d;
    int N;
    boolean[] distChk;
    
    public int func(int weakIdx, int startIdx){ 
        int result = 987654321;
        
        for(int i = 0; i < d.length; i++){
            if(distChk[i] == false){
                distChk[i] = true;
                
                int end = w[weakIdx] + d[i];
                int idx = (weakIdx + 1) % w.length;
                
                while(true){
                    int tmp = 0;
                    if(idx < startIdx) tmp = N;
                    
                    if(w[idx] + tmp <= end){
                        idx = (++idx) % w.length;   
                        if(idx == startIdx)
                            break;
                    }else
                        break;
                }
                
                if(idx == startIdx)
                    result = Math.min(result, 1);
                else
                    result = Math.min(result, 1 + func(idx, startIdx));
                
                distChk[i] = false;
            }   
        }
        return result;
    }
    
    public int solution(int n, int[] weak, int[] dist) {
        int answer = 987654321;
        N = n;
 
        w = new int[weak.length];
        w = weak;
        
        d = new int[dist.length];
        d = dist;
        
        distChk = new boolean[dist.length];
        
        for(int i = 0; i < weak.length; i++)
            answer = Math.min(answer, func(i, i));
        
        if(answer == 987654321) answer = -1;
        return answer;
    }
}