[PROGRAMMERS] 서버 증설 횟수 (JAVA)

- 알고리즘 분류 : DP

- 사용 언어 : JAVA

- 문제 요점

1. dp[i][j]는 i번째 아이템까지 훔쳤고, B의 흔적이 j일 때 A의 최소 흔적을 의미함.
2. A가 훔치면 A의 흔적은 늘고 B는 그대로 → dp[i+1][j]에 업데이트.
3. B가 훔치면 B의 흔적은 늘고 A는 그대로 → dp[i+1][nextB]에 업데이트.
4. Math.min()으로 더 작은 값으로 갱신해 최적 경로 유지.
5. 마지막에 B의 흔적이 조건 M보다 작을 때의 A 최소값이 정답.

public class perfectCrime {
    static final int MAX_VALUE = Integer.MAX_VALUE / 2;

    public static void main(String[] args) {
        int[][] info = {{1, 2}, {2, 3}, {2, 1}};
        int n = 4;
        int m = 4;

        System.out.println(solution(info, n, m));
    }
    static int solution(int[][] info, int n, int m) {
        int itemLength = info.length;
        int[][] dp = new int[itemLength+1][m];

        // dp 초기화
        for (int i = 0; i <= itemLength; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = MAX_VALUE;
            }
        }

        // 0번째 물건을 훔쳤고, a,b 모두 0
        dp[0][0] = 0;
        for (int i = 0; i < itemLength; i++) {
            for (int j = 0; j < m; j++) {
                if (dp[i][j] == MAX_VALUE) {
                    continue;
                }

                int nextA = dp[i][j] + info[i][0];
                if (nextA < n) {
                    dp[i+1][j] = Math.min(nextA, dp[i+1][j]);
                }

                int nextB = j + info[i][1];
                if (nextB < m) {
                    dp[i+1][nextB] = Math.min(dp[i][j], dp[i+1][nextB]);
                }
            }
        }

        int answer = MAX_VALUE;
        for (int j=0; j<m; j++) {
            answer = Math.min(answer, dp[itemLength][j]);
        }
        return answer == MAX_VALUE ? -1 : answer;
    }
}