[프로그래머스 Lv.2] 완전범죄

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

프로그래머스

 

보자마자 KnapSack과 비슷한 느낌이 들어, dp로 해결해보고자 했다.

 

점화식은 아래와 같다.

dp[i][j] = i번째 물건까지 처리했고, B의 흔적이 j일 때, A 흔적의 최솟값

 

왜 dp[][]가 A 정보를 나타나도록 했나?

• 목표가 A의 최솟값이므로, A를 값으로 저장하면 min()으로 갱신 가능
• B는 제약 조건(< m)만 만족하면 되므로 인덱스로 관리

i번째 물건을 처리할 때 다음과 같은 Case가 생긴다.

• A가 훔친다
• B가 훔친다

A가 훔친다.

이전 상태: dp[i-1][j] (B 흔적 = j)
현재 상태: dp[i][j] (B 흔적 변화 없음)
A 흔적: a만큼 증가

→ dp[i][j] = dp[i-1][j] + a

 

 

B가 훔친다.

이전 상태: dp[i-1][j] (B 흔적 = j)
현재 상태: dp[i][j+b] (B 흔적 b만큼 증가)
A 흔적: 변화 없음

→ dp[i][j+b] = dp[i-1][j]

 

따라서 이 둘을 고려한 점화식 사용법은 아래와 같다.

for (int j = 0; j < m; j++) {
    // Case 1: A가 훔친다
    dp[i][j] = min(dp[i][j], dp[i-1][j] + a);
    
    // Case 2: B가 훔친다 (j+b가 m 미만일 때만)
    if (j + b < m) {
        dp[i][j+b] = min(dp[i][j+b], dp[i-1][j]);
    }
}

 

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int solution(vector<vector<int>> info, int n, int m) {
    int size = info.size();
    
    // DP 테이블 초기화
    // dp[i][j]: i번째까지 처리, B 흔적이 j일 때, A 흔적의 최솟값
    vector<vector<int>> dp(size + 1, vector<int>(m, INT_MAX));
    
    // 초기값: 아무것도 안 훔쳤을 때
    dp[0][0] = 0;
    
    // DP 진행
    for (int i = 1; i <= size; i++) {
        int a = info[i - 1][0];  // A가 훔칠 때 흔적
        int b = info[i - 1][1];  // B가 훔칠 때 흔적
        
        for (int j = 0; j < m; j++) {
            // 불가능한 상태면 스킵
            if (dp[i - 1][j] == INT_MAX) continue;
            
            // Case 1: A가 훔친다
            // B 흔적 그대로, A 흔적 증가
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + a);
            
            // Case 2: B가 훔친다
            // B 흔적 증가, A 흔적 그대로
            if (j + b < m) {
                dp[i][j + b] = min(dp[i][j + b], dp[i - 1][j]);
            }
        }
    }
    
    // 모든 물건을 훔친 후, A 흔적의 최솟값 찾기
    int minA = INT_MAX;
    for (int j = 0; j < m; j++) {
        minA = min(minA, dp[size][j]);
    }
    
    // A 흔적도 n 미만이어야 함
    return minA >= n ? -1 : minA;
}