프로그래머스: 완전범죄

전형적인 DFS + DP 문제였다.

DFS로 풀면 시간초과가 나와서 어디에 DP를 적용할지를 고민하는게 핵심이었다.

 

문제를 요약해 보면, 

물건 i를 

A 도둑이 훔치면 info[i][0] 개의 흔적이

B 도둑이 훔치면 info[i][1] 개의 흔적이 남겨진다.

 

이때 모든 물건을 훔치며 

1) A와 B 도둑 각각 n 과 m 이하의 흔적을 남겨 경찰에 붙잡히지 않고

2) A가 남긴 흔적의 개수의 최솟값을 찾는것

 

즉, 각 물건을 A 도둑이 훔쳤을때, B 도둑이 훔쳤을 때는 완전 탐색하면 된다.

 

DP는 같은 물건에 대해서 dp[i][a][b] 값을 탐색했었는지 를 검사했다. dp[i][a][b] 

예를들어, 같은 물건에 대해서 훔쳤을때 dp[i][a][b] =1 이면 더이상 탐색하지 않았다.

 

class Solution {
    static int N =0;
    static int answer;
    static int[][][] dp;
    
    public int solution(int[][] info, int n, int m) {
        answer = Integer.MAX_VALUE;
        
        N = info.length;
        dp = new int[N+1][120][120];
        
        choose(0, 0, 0, n, m, info);
        if(answer == Integer.MAX_VALUE) answer = -1;
        return answer;
    }
    
    
    private void choose(int count, int a, int b, int n, int m, int[][] info) {
        if(dp[count][a][b] == 1)
            return;
        
        if(count == N){
            answer = Math.min(answer, a);
            return;
        }
        
        if(a + info[count][0] < n) {
            choose(count + 1, a + info[count][0], b, n, m, info);
            dp[count+1][a+info[count][0]][b] = 1;
        }
        if(b + info[count][1] < m) {
            choose(count + 1, a, b + info[count][1], n, m, info);
            dp[count+1][a][b + info[count][1]] = 1;
        }
    }
}