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

문제 링크 → 완전범죄 문제 바로가기

---

🗝️ 1. 문제 요약

• A, B 도둑이 모든 물건을 훔쳐야 함
• 각 물건은 A 또는 B 중 하나만 훔칠 수 있음
• A 도둑 흔적 누적합 < n
• B 도둑 흔적 누적합 < m
• 조건을 지키며 A의 흔적 누적합을 최소화해야 함
• 조건 만족 불가 시 -1 반환

---

⚠️ 2. 입출력 예제 분석

입력

info = [[1, 2], [2, 3], [2, 1]];
n = 4;
m = 4;

---

📊 3. DP 상태 저장표 시뮬레이션

dp[a][b] = A도둑 누적 흔적 a, B도둑 누적 흔적 b일 때 도달 가능 여부를 의미하며,
A 도둑 누적 흔적의 최소합을 추적합니다.
n = 4, m = 4 → 배열 크기는 4 x 4

✅ 초기 상태

dp[0][0] = 0 (시작 상태)

---

🧩 1단계: 첫 번째 물건 ([1, 2])

• A가 훔침 → A +1 = 1, B 그대로 → dp[1][0] = 1
• B가 훔침 → A 그대로, B +2 = 2 → dp[0][2] = 0

A \ B	0	1	2	3
0			0
1	1
2
3

---

🧩 2단계: 두 번째 물건 ([2, 3])

• 기존 상태: dp[1][0] = 1, dp[0][2] = 0

(1,0) 기준

• A가 훔침 → A: 1+2=3, B:0 → dp[3][0] = 3
• B가 훔침 → B: 0+3=3 → dp[1][3] = 1

(0,2) 기준

• A가 훔침 → A: 0+2=2, B:2 → dp[2][2] = 2
• B가 훔침 → B: 2+3=5 → 초과 → 제외

A \ B	0	1	2	3
0
1				1
2			2
3	3

---

🧩 3단계: 세 번째 물건 ([2, 1])

• 기존 상태: dp[3][0]=3, dp[1][3]=1, dp[2][2]=2

(3,0)

• A가 훔침 → A: 3+2=5 → 초과 → 제외
• B가 훔침 → B: 0+1=1 → dp[3][1] = 3

(1,3)

• A가 훔침 → A: 1+2=3 → dp[3][3] = 3
• B가 훔침 → B: 3+1=4 → 초과 → 제외

(2,2)

• A가 훔침 → A: 2+2=4 → 초과 → 제외
• B가 훔침 → B: 2+1=3 → dp[2][3] = 2

A \ B	0	1	2	3
0
1
2				2
3		3		3

---

✅ 최종 결과

유효한 상태:

• dp[2][3] = 2
• dp[3][1] = 3
• dp[3][3] = 3

→ 이 중 A 도둑 흔적 최소는 **2** → 정답

---

💡 최적화 코드 (2차원 DP)

import java.util.*;

class Solution {
    public int solution(int[][] info, int n, int m) {
        int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[n][m];
        for (int[] row : dp) Arrays.fill(row, INF);
        dp[0][0] = 0;

        for (int[] item : info) {
            int aTrace = item[0], bTrace = item[1];
            int[][] nextDp = new int[n][m];
            for (int[] row : nextDp) Arrays.fill(row, INF);

            for (int a = 0; a < n; a++) {
                for (int b = 0; b < m; b++) {
                    if (dp[a][b] == INF) continue;

                    if (a + aTrace < n) {
                        nextDp[a + aTrace][b] = Math.min(nextDp[a + aTrace][b], dp[a][b] + aTrace);
                    }
                    if (b + bTrace < m) {
                        nextDp[a][b + bTrace] = Math.min(nextDp[a][b + bTrace], dp[a][b]);
                    }
                }
            }
            dp = nextDp;
        }

        int minA = INF;
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < m; b++) {
                minA = Math.min(minA, dp[a][b]);
            }
        }

        return minA == INF ? -1 : minA;
    }
}

---

🔍 정리

구분	설명
상태 정의	dp[a][b] → A, B의 누적 흔적 상태
목표	a < n, b < m 조건 내에서 A의 누적 흔적 최소
접근법	DP로 상태 확장하며 최소값 유지
결과	최소 A 도둑 흔적 = 2