[Programmers] 완전범죄 - Java

문제

프로그래머스

 

풀이

이 문제 좀 어려웠다...

처음에는 이 문제를 그리디와 같은 접근을 했다. B의 흔적을 최대화 하고, A의 흔적을 최소해야하니까, B가 남길 수 있는 흔적을 높게 -> A가 남길 수 있는 흔적을 낮게 하는 방식으로 정렬을 해서 문제를 해결하려고했었다.

 

하지만 이 문제에 테스트케이스를 보고 종이에 조금만 적어서 생각을 해보면 그 방법이 될 수 없다는 것을 알게되었다.

 

DP라는 점을 눈치 챘는데 이유는 다음과 같다.

1. 물건을 훔친다 /  훔치지 않는다? => 뭔가 2차원 배열을 사용해서 점화식을 정의할 것 같다는 생각이 든다.

2. 물건을 훔쳤을때, 훔치지 않을때의 기준을 정의하기가 어려워서 훔친 경우의 수와 훔치지 않은 경우의 수 두가지를 모두 구해야할 것이라는 생각이 들었지만, 점화식을 정의하지 못했다. 

 

그래서 구글 신에게 검색해서 DP 고수분들이 푼 코드를 참고했다.

 

dp[i][j] : i번째까지의 물건을 훔치면서 B 흔적 총합이 j일때 A 흔적의 최솟값

 

여기서 제일 중요한 것은 A 흔적의 최솟값이라는 것이다.

A가 훔쳤다고 해보자.

dp[i][j] = min(dp[i - 1][j] + a, dp[i][j])이다.

i를 훔치기 직전에 B 흔적 총합이 j일때(dp[i - 1][j])에서 현재 a의 흔적을 더한 것과 dp[i][j] 중 최솟값을 비교하면 된다.

 

B가 훔쳤다고 해보자.

dp[i][j + B 흔적] = min(dp[i][j + B 흔적], dp[i - 1][j])이다.

dp[i][j]는 A 흔적의 최솟값이기 때문에, 인덱스만 더해주면 된다. dp[i - 1][j]란, i 이전에 B 흔적의 총합이  j일때의 A흔적의 최솟값이므로, 

 

i번째 까지의 물건을 B가 훔쳤을 경우의 수 vs i이전까지의 물건을 훔쳤는데, B 흔적의 총합이 J일때의 경우의 수를 비교해주면 된다.

 

혹시 더 명확하게 설명해주실 분이 계시다면, 댓글을 달아주셔서 조언을 해주셔도 됩니다!!

 

소스코드

import java.util.*;

class Solution {
    private static final int INF = 987654321;
    
    public int solution(int[][] info, int n, int m) {
        int thingsCnt = info.length;
        
        int[][] dp = new int[thingsCnt + 1][m];
        
        for (int i = 0; i <= thingsCnt; i++) {
            Arrays.fill(dp[i], INF);
        }
        
        //0번째까지의 물건을 처리, B흔적 총합이 0일때 0(물건 안훔침)
        dp[0][0] = 0;
        
        for (int i = 1; i <= thingsCnt; i++) {
            int a = info[i - 1][0];
            int b = info[i - 1][1];
            
            for (int j = 0; j < m; j++) {
                //a가 훔쳤을때,
                dp[i][j] = Math.min(dp[i - 1][j] + a, dp[i][j]);
                
                //b가 훔쳤을때, (흔적이 m보다 작아야한다는 점에 유의)
                if (j + b < m) {
                    dp[i][j + b] = Math.min(dp[i - 1][j], dp[i][j + b]);
                }
            }
        }
        
        int answer = INF;
        
        for (int j = 0; j < m; j++) {
            answer = Math.min(dp[thingsCnt][j], answer);
        }
        
        return answer >= n ? -1 : answer;
    }
}