완전범죄

2025-03-30

#JAVA#프로그래머스

문제 링크

문제 풀이 시간 : 1시간 이상

문제 풀이 :

문제를 읽고나서 바로 이건 조합으로 풀면 안되겠다 라고 생각했지만

생각나는 풀이 방법이 이거 밖에 없어서 일단 코드를 짰다.

초기 코드

Java

class Solution {
    public int[][] INFO;
    public int N, M, ans = Integer.MAX_VALUE;
    
    public void find(int idx, int sumA, int sumB){
        if(N<=sumA || M<=sumB){
            return;   
        }
        if(idx == INFO.length){
            ans = Math.min(ans, sumA);
            return;
        }
        
        find(idx+1,sumA+INFO[idx][0],sumB);
        find(idx+1,sumA,sumB+INFO[idx][1]);
    }
    
    
    public int solution(int[][] info, int n, int m) {
        int answer = 0;
        INFO = info;
        N = n;
        M = m;
        
        find(0,0,0);
        
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

당연하게도 시간초과가 나고 40점을 받았다.

뭔가 dp로 해야된다는건 알겠는데

풀이방법을 모르겠다.

그래서 결국 검색찬스를 썼다.

여기서 dp[i][j] 배열은 i번째 물건을 훔쳤을 때, B의 흔적의 합이 j이고, A의 흔적의 합이 dp[i][j]인 것이다.

각 물건에 대해 우리가 고려할 상황은 두가지이다.

1
A가 훔친 경우

2
B가 훔친 경우

A가 훔친 경우

이전 상태 = dp[i-1][j]: 물건 i-1개까지 훔쳤고, B 도둑의 흔적의 합은 j

A 도둑이 i번째 물건을 훔치면

•
B 도둑의 흔적은 그대로 j

•
A 도둑의 흔적은 기존보다 +A 증가

그래서 현재 상태 dp[i][j]를 dp[i-1][j] + A로 갱신한다

B가 훔친 경우

이전 상태 → dp[i-1][j]: 물건 i-1개까지 처리했고, B 도둑의 흔적은 j

B 도둑이 i번째 물건을 훔치면,

•
B 도둑의 흔적은 j + B로 증가

•
A 도둑의 흔적은 그대로 유지

그래서 현재 상태 dp[i][j + B]를 dp[i-1][j]로 갱신한다

그래서 마지막에 아래와 같은 코드로 모든 물건을 훔쳤을 때 A가 남긴 흔적의 최솟값을 구해주면 된다.

Java

for(int i=0;i<m;i++){
	answer = Math.min(answer, dp[info.length][i]); //A가 남긴 흔적의 최솟값
}

최종 코드

Java

import java.util.*;

class Solution {
    public int solution(int[][] info, int n, int m) {
        int answer = Integer.MAX_VALUE;
        
        int[][] dp = new int[info.length+1][m];
        
        for(int i=0;i<info.length+1;i++){
            Arrays.fill(dp[i],1000000);
        }
        
        dp[0][0] = 0;
        
        for(int i=1;i<info.length+1;i++){
            int A = info[i-1][0]; //A가 훔칠 경우 흔적
            int B = info[i-1][1]; //B가 훔칠 경우 흔적
            for(int j=0;j<m;j++){
                dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+A); //A가 훔칠 경우 
                
                if(j+B<m){ //B가 훔칠 경우 흔적의 합이 m을 넘으면 안됨
                    dp[i][j+B] = Math.min(dp[i][j+B], dp[i-1][j]);
                }
            }
        }
        
        for(int i=0;i<m;i++){
            answer = Math.min(answer, dp[info.length][i]); //A가 남긴 흔적의 최솟값
        }
        
        return answer < n ? answer : -1;
    }
}