[프로그래머스] 완전 범죄

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

프로그래머스

 

 

문제

도둑 A와 도둑 B가 경찰에 붙잡히지 않고 모든 물건을 훔쳐야 한다. 이때 도둑 A가 남긴 누적 흔적의 최솟값을 구한다.
만약 두 도둑 모두 경찰에 붙잡히지 않고 모든 물건을 훔칠 수 없으면 -1을 반환한다.

 

조건

1. 각 물건을 도둑이 훔쳤을 때 남기는 흔적의 개수는 도둑 A는 `info[i][0]`, 도둑 B는 `info[i][1]`이다.

2. 도둑 A는 n 미만으로 흔적을 남길 수 있고, 도둑 B는 m 미만으로 흔적을 남길 수 있다.

 

처음 접근: A가 훔칠 수 있는 모든 조합을 구하자

처음에는 단순하게 생각했다.

1. 일단 A가 안 들키고 훔칠 수 있는 물건 조합을 구하고
2. 그 조합 외 물건을 모두 B가 안 들키고 훔칠 수 있다면
3. A의 누적 흔적값을 기존 저장값과 비교해서 작은 값을 업데이트한다.

이렇게 되면 백트래킹으로 모든 조합을 구하게 되므로 아마 시간 초과가 나겠다고 생각했지만 달리 생각나는 방법이 없어서 일단 구현했다.

 

그리고 구현하면서 A가 아무것도 훔치지 않고 B만 모든 물건을 훔쳤을 경우에 대한 로직도 추가해 주었다.

class Solution {
    static Set<Set<Integer>> a = new HashSet<>();
    
    public int solution(int[][] info, int n, int m) {      
        int answer = Integer.MAX_VALUE;
        
        //A가 안잡히고 훔칠 수 있는 모든 물건 조합
        for(int i=0; i<info.length; i++) {
            makeComb(info, n, i, info[i][0], new HashSet<>(List.of(i)));
        }
        
        //A 조합에서 훔친 물건 빼고 B가 안잡히고 모두 훔칠 수 있는지 확인 
        if(a.isEmpty()) {
            int be = 0;
            for(int[] i : info) {
                be += i[1];
                if(be >= m) return -1;
            }
            return 0;
        }
        
        for(Set<Integer> stole : a) {
            int ae = 0, be = 0;
            for(int i=0; i<info.length; i++) {
                if(stole.contains(i)) ae += info[i][0];
                else be += info[i][1];
            }
            
            if(!isArrested(n, ae) && !isArrested(m, be)) answer = Math.min(ae, answer);
        }
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    void makeComb(int[][] info, int n, int curr, int evid, Set<Integer> list) {
        if(isArrested(n, evid)) return;
        else a.add(new HashSet<>(list));
        
        for(int i=curr+1; i<info.length; i++) {
            list.add(i);
            makeComb(info, n, i, evid+info[i][0], list);
            list.remove(Integer.valueOf(i));
        }
    }
    
    boolean isArrested(int limit, int sum) {
        return sum >= limit;
    }
}

 

예상대로 시간초과가 나기도 했고,

코드를 보다 보니 그때그때 B가 붙잡히는지 확인한다면 굳이 Set에 만든 조합을 저장해 줄 필요가 없다고 생각했다.

 

비효율적이라고 생각된 부분:

1. 계속 List로 조합을 만드느라 원소 추가/제거하는 부분

2. 만든 조합을 Set에 저장하는 부분

3. 그리고 조합 만드는 반복문(dfs)이 완전히 종료된 후에 만들어진 조합을 가지고 다시 흔적에 대해 계산하는 부분

 

List나 Set를 쓰지 않고 dfs 안에서 반복문 진행할 때 처리할 수 있는 부분이라고 생각되어서 다시 고민해 봤다.

 

두 번째 접근: 어떤 물건을 A와 B가 훔쳤을 경우에 대해 각각 DFS를 수행하자

흔적합을 다시 계산하는 부분과 List, Set에 대한 문제를 해결하는 방향으로 생각해 보니까 DFS를 각각의 경우에 대해 수행해 주면 되겠다는 생각이 들었다.

훔쳐야 할 물건을 차례로 A, B 각각이 훔쳤을 경우의 누적합을 계산해 넘겨서 붙잡히는지 확인하면 된다.

class Solution {
    int limitA, limitB;
    
    int answer = Integer.MAX_VALUE; //A의 최소 누적 흔적합
    
    public int solution(int[][] info, int n, int m) {
        limitA = n; limitB = m;
        
        //각 물건을 a와 b가 훔쳤을 때의 경우의 수를 모두 진행 
        dfs(info, 0, info[0][0], 0);
        dfs(info, 0, 0, info[0][1]);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    void dfs(int[][] info, int idx, int evidA, int evidB) {
    	//둘 중 하나라도 잡혔으면 실패 
		if(evidA < limitA && evidB < limitB) return;
    
        //모든 물건을 훔쳤으면 둘 모두 잡히지 않는지 확인
        if(idx == info.length-1) {
            if(evidA < limitA && evidB < limitB) answer = Math.min(answer, evidA);
            return;
        }
        
        dfs(info, idx+1, evidA+info[idx+1][0], evidB);
        dfs(info, idx+1, evidA, evidB+info[idx+1][1]);
    }
}

 

훨씬 코드가 간결해졌다.

진행 중에 도둑 중 하나라도 경찰에 붙잡힌 경우라면 그 이상 진행해도 불가능하므로 가지치기해 주고,

물건에 대한 인덱스(idx)가 물건 목록 길이-1이 되면 모든 물건을 훔친 상황이니까 그때 흔적합을 확인해서 작은 값으로 업데이트해 줬다.

 

그러나 여전히 시간 초과가 났고👹, 계산 수행을 더 쳐낼 수 있는 부분 고민 시작.... 

 

마지막 접근: 각 경우의 수에 대한 수행 여부를 저장하자

이 정도 되면 dp 배열 사용... 쪽으로 생각이 기울어서 뭔가 값을 배열을 저장해 놨다가 써먹으라는 건가?!!!!라는 갑작스런 생각이 들어서 배열을 활용할 수 있는 방향으로 고민해 봤다.

 

생각나는 부분은

1. 각 물건에 대해 A의 누적합 x와 B의 누적합 y의 경우일 때 방문한 적이 있는지

2. 방문했다면 그때 결과가 어땠는지에 따라 계산을 더 진행할지에 대해 배열을 활용하면 되지 않을까......

class Solution {
    int limitA, limitB;
    
    int answer = Integer.MAX_VALUE; //A의 최소 누적 흔적합
    int[][][] dp;
    
    public int solution(int[][] info, int n, int m) {
        limitA = n; limitB = m;
        
        dp = new int[info.length][1001][1001]; //0:미방문, 1:가능, 2:불가능
        
        //각 물건을 a와 b가 훔쳤을 때의 경우의 수를 모두 진행 
        dfs(info, 0, info[0][0], 0);
        dfs(info, 0, 0, info[0][1]);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    boolean dfs(int[][] info, int idx, int evidA, int evidB) {
        if(dp[idx][evidA][evidB] == 2) return false;
        if(evidA >= limitA || evidB >= limitB) return false;
        
        //모든 물건을 훔쳤으면 둘 모두 잡히지 않는지 확인
        if(idx == info.length-1) {
            if(evidA < limitA && evidB < limitB) answer = Math.min(answer, evidA);
            return true;
        }
        
        dp[idx][evidA][evidB] = dfs(info, idx+1, evidA+info[idx+1][0], evidB) ? 1 : 2;
        dp[idx][evidA][evidB] = dfs(info, idx+1, evidA, evidB+info[idx+1][1]) ? 1 : 2;
        
        return false;
    }
}

 

이렇게 이미 방문해서 불가능이라고 결론 내린 경우에 대해서는 더 이상 파고들지 않는 방향으로 구현하니까 통과된다. 🫨