[programmers] 완전범죄

11 May 2023 in Algorithm on Algorithm

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

import java.util.Arrays;

class Solution {
    public int solution(int[][] info, int n, int m) {
        int itemCount = info.length;
        int[][] dp = new int[itemCount + 1][m];
        int INF = n;

        // 초기화
        for (int i = 0; i <= itemCount; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][0] = 0;

        // DP 수행
        for (int i = 1; i <= itemCount; i++) {
            int aTrace = info[i - 1][0];
            int bTrace = info[i - 1][1];
            for (int j = 0; j < m; j++) {
                // A가 훔치는 경우
                if (dp[i - 1][j] + aTrace < dp[i][j]) {
                    dp[i][j] = dp[i - 1][j] + aTrace;
                }
                // B가 훔치는 경우
                if (j + bTrace < m && dp[i - 1][j] < dp[i][j + bTrace]) {
                    dp[i][j + bTrace] = dp[i - 1][j];
                }
            }
        }

        // 결과 계산
        int minATrace = INF;
        for (int j = 0; j < m; j++) {
            if (dp[itemCount][j] < minATrace) {
                minATrace = dp[itemCount][j];
            }
        }

        return minATrace >= n ? -1 : minATrace;
    }
}