[프로그래머스] 완전범죄 자바 DP 방식

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

프로그래머스

 

문제

info는 아이템 별 흔적값들의 모음이며 info[i][0]은 A의 흔적값, [i][1]은 B의 흔적값이다.

A의 누적 흔적값 >= n 일 때와 B의 누적 흔적값 >= m 일때 경찰에 발각된다.

모든 물건을 훔치려고 할 때, 경찰에 발각되지 않는 선에서 A의 최소 누적 흔적값을 구하여라.

단 A B 둘다 모두 훔칠 수 없는 경우 -1을 반환한다.

접근

1.info.length와 같은 길이의 String[] whoSteal을 하나 생성하여 해당 아이템을 누가 훔쳤는지 저장한다.
2. info를 순회하며, m > bPoint + item[i] 일 때 "b" , n > aPoint + item[0] 일떄 "a" 를 whoSteal에 저장.
둘 다 불가능할경우 -1을 리턴.
3. whoSteal을 순회하며 a가 훔친 값들을 info 에서 꺼내서 더한다.

public int solution(int[][] info, int n, int m) {
        String[] whoSteal = new String[info.length];
        int aPoint = 0;
        int bPoint = 0;
        for(int i = 0 ; i < info.length; i ++){
            int[] item = info[i];
            if(m > bPoint + item[1]){
                whoSteal[i] = "b";
                bPoint += item[1];
            } else if(n > aPoint + item[0]){
                whoSteal[i] = "a";
                aPoint += item[0];
            } else {
                //a, b 둘다 불가
                return -1;
            }
        }
        int result = 0;
        for(int i = 0; i < whoSteal.length; i ++){
            if("a".equals(whoSteal[i])){
                result += info[i][0];
            }
        }
        return result;
    }

발견된 문제 : 실제 제출시 실패

❗ 실패 케이스 원인 요약
당신의 코드에서는 항상 먼저 b가 도전하고, b가 못 하면 a가 도전합니다. 하지만 이런 방식은 최적의 선택을 보장하지 않습니다.

수정

도통 이해가 되지 않아 기존에 해결을 한 다른 블로그의 소스를 참고하였다..
아직 100% 이해하진 못했으나 클리어는 가능함을 확인하였다.

static final int INF = 100000;
public int blogsolution(int[][] info, int n, int m) {
    int size = info.length;
    int [][] dp = new int [size+1][m];
    for(int i = 0; i <= size; i++){
        Arrays.fill(dp[i], INF);
    }
    dp[0][0] = 0; //// 물건 0개, B의 흔적 0 → A의 흔적도 0
    for(int i = 1; i <= size; 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][j], dp[i-1][j] + a);
            // b 선택
            if(j + b < m){
                dp[i][j + b] = Math.min(dp[i][j + b], dp[i-1][j]);
            }
        }
    }

    //갱신 끝 정답찾기.
    int min = INF;
    for(int j = 0; j < m; j++){
        min = Math.min(dp[size][j], min);
    }
    return min >= n ? -1 : min;
}

 

소스출처: https://20240228.tistory.com/435

---

해답 소스 해석

🧩 핵심 아이디어: DP

• DP 상태 정의:
  dp[i][j] = k
  → i번째까지의 물건을 처리했을 때, B의 흔적 총합이 j인 상황에서 A의 흔적 총합의 최소값이 k
• INF (100000): 불가능한 상태를 나타냄

---

🧱 코드 구조 설명

🔹 초기화

int size = info.length; 
int [][] dp = new int [size+1][m]; // B의 흔적은 최대 m-1까지만 허용 

for(int i = 0; i <= size; i++){ 
	Arrays.fill(dp[i], INF); 
} 
dp[0][0] = 0; // 물건 0개, B의 흔적 0 → A의 흔적도 0 (기본 상태)

 

---

🔹 DP 갱신 (점화식)

예시 흐름:

• dp[i-1][j]는 이전 상태
• a가 훔치면 → A의 흔적 증가 (+a), B는 그대로
• b가 훔치면 → A는 그대로, B의 흔적 증가 (+b)
• 조건: B의 흔적은 m 미만까지만 유효하므로 j + b < m 확인

---

🔹 정답 찾기

//갱신 끝 정답찾기.
int min = INF;
for(int j = 0; j < m; j++){
    min = Math.min(dp[size][j], min); //마지막 row에서 최소값을 찾는다.
}
return min >= n ? -1 : min;

• 마지막 줄은 "모든 물건을 처리했을 때" (dp[size][j])
• B의 흔적이 조건을 만족하는 상태들 중, A의 흔적이 가장 작은 값을 선택
• 만약 그 값이 A의 제한 n을 넘는다면 실패 → -1 반환

---

⏱ 시간복잡도

• O(N * M) → N은 물건 개수, M은 B의 최대 흔적 수 (m)
• 최대: 40 * 120 = 4800 → 굉장히 빠름

---

✅ 결론 정리

요소의미

dp[i][j]	i번째 물건까지 처리했을 때, B의 흔적이 j일 경우 A의 최소 흔적
dp[0][0] = 0	아무 물건도 훔치지 않았을 때의 시작점
INF	불가능한 상태를 초기화하는 값
갱신 로직	A가 훔치면 A + a / B가 훔치면 B + b
결과 처리	A의 최소 흔적 중 n 미만인 값 선택