[알고리즘] 프로그래머스 완전범죄 (Java)

프로그래머스 완전범죄
일단 대충이라도 적어보는 중이다..(나중에 내가 수정하겠지?)

문제 설명

A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다. 단, 각 도둑이 물건을 훔칠 때 남기는 흔적이 누적되면 경찰에 붙잡히기 때문에, 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.

물건을 훔칠 때 조건은 아래와 같습니다.

물건 i를 훔칠 때,
A도둑이 훔치면 info[i][0]개의 A에 대한 흔적을 남깁니다.
B도둑이 훔치면 info[i][1]개의 B에 대한 흔적을 남깁니다.
각 물건에 대해 A도둑과 B도둑이 남기는 흔적의 개수는 1 이상 3 이하입니다.
경찰에 붙잡히는 조건은 아래와 같습니다.

A도둑은 자신이 남긴 흔적의 누적 개수가 n개 이상이면 경찰에 붙잡힙니다.
B도둑은 자신이 남긴 흔적의 누적 개수가 m개 이상이면 경찰에 붙잡힙니다.
각 물건을 훔칠 때 생기는 흔적에 대한 정보를 담은 2차원 정수 배열 info, A도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 n, B도둑이 경찰에 붙잡히는 최소 흔적 개수를 나타내는 정수 m이 매개변수로 주어집니다. 두 도둑 모두 경찰에 붙잡히지 않도록 모든 물건을 훔쳤을 때, A도둑이 남긴 흔적의 누적 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 어떠한 방법으로도 두 도둑 모두 경찰에 붙잡히지 않게 할 수 없다면 -1을 return해 주세요.

제한사항

1 ≤ info의 길이 ≤ 40
info[i]는 물건 i를 훔칠 때 생기는 흔적의 개수를 나타내며, [A에 대한 흔적 개수, B에 대한 흔적 개수]의 형태입니다.
1 ≤ 흔적 개수 ≤ 3
1 ≤ n ≤ 120
1 ≤ m ≤ 120

문제풀이

1) dfs

그리디로 풀었는데 최악의 경우 2^40 (1조)라서 시간초과가 난다..

2) dp 2차원 (like 배낭문제)

배낭문제에서는 아래와 같이 설정 후,
가로 : 물건의 순서(가치, 무게)
세로 : 배낭의 최대 무게
dp[i][w] = 최대무게가 w인 가방에서 i번째 물건까지 판단했을 때의 최대 가치로 구현한다.

해당 문제를 자세히 생각해보면 배낭문제랑 다를게 없다..
나도 처음에 dp 2차원 같은데,, x랑 y를 뭘로 설정해야하지로 고민했다.

그럼 위에 문제도
가로 : 물건의 순서(a흔적, b흔적)
세로 : b 흔적의 누적 개수 (m-1까지)
dp[i][m] : 경찰에게 들키지 않는 누적 흔적이 m인 상황에서 i번째 물건까지 판단했을 때의 a의 최소 가치로 구현하면 된다.

그럼 이제 모든 물건과 m을 늘려가면서 dp를 채우면 된다.
-> m이 b흔적보다 작은 경우는 a가 물건을 훔칠 수 밖에 없기 때문에 a가 항상 물건을 훔진다.
-> 그렇지 않다면 과거의 물건을 훔친 기록에서 데이터를 가져와서 작은값으로 업데이트한다.

import java.util.*;
class Solution {
    public int solution(int[][] info, int n, int m) {
        int answer = n;
        int len = info.length;
        int[][] dp = new int[len+1][m];
        for(int i = 1; i < len+1; i++) {
            int a = info[i-1][0];
            int b = info[i-1][1];
            
            for(int j = 0; j < m; j++) {
                if(j < b) {
                    dp[i][j] = dp[i-1][j] + a; 
                    continue;
                }
                dp[i][j] = Math.min(dp[i-1][j-b], dp[i-1][j]+a);
            } 
        }
        
        for(int i = 0; i < m; i++) {
            answer = Math.min(answer, dp[len][i]);
        }

        return answer >= n ? -1 : answer;
    }
}

3) dp 1차원

배낭문제 dp를 2차원에서 1차원으로 바꿀때는 index를 뒤에서 접근하는 것만 신경쓰면 된다. (배낭 2차원에서 dp [i][j] = (i+1의 w) + dp [i-1][j-m] 이기 때문에 1차원으로 바꿀 경우 앞에 값을 먼저 업데이트 하면 안된다.)

import java.util.*;
class Solution {
    public int solution(int[][] info, int n, int m) {
        int answer = n;
        int len = info.length;
        int[] dp = new int[m];
        
        for(int i = 0; i < len; i++) {
            int a = info[i][0];
            int b = info[i][1];
            for(int j = m-1; j >= 0; j--) {
                if(j < b) dp[j] += a;
                else dp[j] = Math.min(dp[j-b], dp[j]+a);
            }
        }
        
        for(int i = 0; i < m; i++) {
            answer = Math.min(answer, dp[i]);
        } 

        return answer >= n ? -1 : answer;
    }
}

시간 복잡도 O(info의 길이 * M) = (40 * 1200) = 48,000 정도 된다.