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

문제

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

프로그래머스

 

---

 

문제 개요

A도둑과 B도둑은 협력하여 모든 물건을 훔치려 합니다. 하지만 물건을 훔칠 때마다 각 도둑에게 흔적이 남으며, 이 흔적이 기준 이상으로 누적되면 경찰에 붙잡히게 됩니다.

• A가 훔치면 info[i][0]만큼 A의 흔적이 쌓인다.
• B가 훔치면 info[i][1]만큼 B의 흔적이 쌓인다.

목표는 모든 물건을 도둑질하되, A와 B 모두 경찰에 붙잡히지 않도록 하면서 A의 흔적 합계를 최소화하는 것입니다.

 

 

접근 방법

이 문제는 각 물건마다 A 또는 B 중 누가 훔칠지를 결정하면서, A의 누적 흔적을 최소화하는 것이 목표입니다. 단, 두 도둑 모두 경찰에 붙잡히지 않아야 하므로, 각각의 흔적 누적치를 제한 조건 이내로 유지해야 합니다.

이를 위해 동적 계획법(DP)을 활용해 다음과 같이 상태를 정의합니다:

• dp[b] : B가 현재까지 남긴 흔적이 b일 때, A의 누적 흔적의 최솟값
  • 여기서 b는 B의 누적 흔적입니다.
  • dp[b]의 값은 해당 상황에서의 A의 누적 흔적 최소값을 의미합니다.

초기 상태는 dp[0] = 0 (두 도둑 모두 흔적이 없는 상태)이고, 이후 각 물건에 대해 아래 두 가지 선택지를 고려합니다:

1. A가 물건을 훔치는 경우
   • A의 흔적은 dp[b] + info[i][0]로 증가
   • B의 흔적은 그대로 b
   • 단, A의 누적 흔적이 n 미만이어야 함
2. B가 물건을 훔치는 경우
   • A의 흔적은 변하지 않고 dp[b] 유지
   • B의 흔적은 b + info[i][1]로 증가
   • 단, B의 누적 흔적이 m 미만이어야 함

이 과정을 각 물건에 대해 반복하면서, 가능한 모든 흔적 조합 상태를 업데이트합니다. 모든 물건을 처리한 뒤, B의 흔적이 0부터 m - 1까지인 dp[b] 중 A의 누적 흔적이 가장 작은 값을 정답으로 선택하면 됩니다.

 

코드

import java.util.*;
class Solution {
    static int[] dp;
    public int solution(int[][] info, int n, int m) {
        int answer = Integer.MAX_VALUE;
        //n,m이 120 이하이기 때문
        dp = new int[121];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        dp(info, n, m);
        
        for(int i=0; i<m; i++) {
            answer = Math.min(answer, dp[i]);
        }
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    public void dp(int[][] info, int n, int m) {
        for(int[] arr : info) {
            int aRoot = arr[0];
            int bRoot = arr[1];
            int[] next = new int[121];
            Arrays.fill(next, Integer.MAX_VALUE);
            
            for(int b=0; b<121; b++) {
                if(dp[b] == Integer.MAX_VALUE) continue;
                
                if(dp[b] + aRoot < n) {
                    next[b] = Math.min(next[b], dp[b] + aRoot);
                }
                
                if(b + bRoot < m) {
                    next[b + bRoot] = Math.min(next[b + bRoot], dp[b]);
                }
            }
            
            dp = next;
        }
    }
}