[프로그래머스] 완전범죄(Java)

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

프로그래머스

---

문제 풀이

DP로 풀이, 처음 점화식을 세우는게 어려워 다른 블로그를 참고했다.

 

점화식 : dp[x][y] = z

x개의 물건을 훔쳤을 때, B도둑의 흔적 개수는 y, A도둑의 흔적 개수는 z

 

import java.util.*;

class Solution {
		public int solution(int[][] info, int n, int m) {
			int maxVal = 100000;

			// 점화식 dp[x][y]: z
			// x개의 물건을 훔쳤을 때, B도둑의 흔적 개수는 y, A도둑의 흔적 개수는 z
			int dp[][] = new int[info.length+1][m];

			// dp 배열 초기화
			for(int i=0; i<info.length+1; i++) {
				Arrays.fill(dp[i], maxVal);
			}

			dp[0][0] = 0;

			for(int i=1; i<=info.length; i++) {
				int thiefA = info[i-1][0];
				int thiefB = info[i-1][1];

				for(int j=0; j<m; j++) {
					// A도둑이 훔쳤을 경우
					dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + thiefA);

					// B도둑이 훔쳤을 경우
					if(j+thiefB < m) {
						dp[i][j+thiefB] = Math.min(dp[i][j+thiefB], dp[i-1][j]);
					}
				}
			}

			int answer = maxVal;
			for(int j = 0; j < m; j++){
				answer = Math.min(dp[info.length][j], answer);
			}
            
			if(answer >= n) {
				return -1;
			} else {
				return answer;
			}
		}
	}