완전범죄

https://school.programmers.co.kr/learn/courses/30/lessons/389480?language=java

프로그래머스

 

처음에 백트래킹을 사용해 풀었는데 시간초과가 났다. info의 길이가 40 이하인 것을 보고, dp를 사용해야 한다는 것을 알았다.

 

2차원 dp로 선언할 경우, 시행횟수를 카운트할 수 없다는 것을 깨닫고, 시행횟수를 포함한 3차원 dp를 만들기로 결정했다.

 

import java.util.*;
class Solution {
    static int INF = 1000000;

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

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

        for (int k = 0; k < itemCnt; k++) {
            int aTrace = info[k][0];
            int bTrace = info[k][1];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (dp[k][i][j] == INF) continue;

                    // A가 훔치는 경우
                    int ni = i + aTrace;
                    if (ni < n) {
                        dp[k + 1][ni][j] = Math.min(dp[k + 1][ni][j], dp[k][i][j] + aTrace);
                    }

                    // B가 훔치는 경우
                    int nj = j + bTrace;
                    if (nj < m) {
                        dp[k + 1][i][nj] = Math.min(dp[k + 1][i][nj], dp[k][i][j]);
                    }
                }
            }
        }

        int answer = INF;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                answer = Math.min(answer, dp[itemCnt][i][j]);
            }
        }

        return (answer == INF) ? -1 : answer;
    }
}