[프로그래머스] 동전 교환 (java, DP)

문제

문제 설명
여러 종류의 동전을 나타내는 정수 배열 coins가 주어집니다. 또한, amount라는 총 금액이 주어집니다.

이 금액을 만들기 위해 필요한 최소 동전의 수를 반환하세요. 만약 이 금액을 주어진 동전으로 만들 수 없다면 -1을 반환하세요.

각 동전의 개수는 무한히 많다고 가정할 수 있습니다.

제한 사항

-1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

 

입출력 예

coins	    amount	return
[1, 2, 5]	11	3
[2]	        3	-1
[1]	        0	0

 

입출력 예 설명

입출력 예#1
11 = 5 + 5 + 1

입출력 예#2
주어진 coins로는 amount를 충족시킬 수 없습니다.

입출력 예#3
amount가 0이므로 필요한 코인은 없습니다.

문제 분석

문제 파악

• 동전 종류 : coins 배열 (1≤coins[i]≤231-1)
• 목표 동전 금액 : amount

동전을 사용하여 목표 동전 금액을 도달하는 최소 동전 개수 구하기

접근 방법

• 1차원 BFS로도 접근 가능
• DP 접근은 아래와 같다.

0부터 amount 까지 순회하면서 동전을 넣어본다.
	amount 값이 없는 경우 도달하지 않은 것이므로 이 경우는 따지지 말아야 한다.
	동전이 음수인 경우는 없으므로 amount를 초과하는 경우에는 amount에 도달할 수 없다.
	
amount 지점에 도달한 적이 없는 경우 -1 출력
amount 지점에 도달한 경우 그 인덱스값을 출력

ex) [1,2,5] 이고 amount = 11 이라면, 아래 그림과 같다.

 

정답 코드

import java.util.*;

class Solution {
    public int solution(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        // basecase
        dp[0] = 0;
        // 점화식
        for(int i=0; i<amount; i++) { // 0부터 amount 까지 순회하면서 
            for(int coin : coins) { // 가능한 동전을 넣어본다.
                if(dp[i] == Integer.MAX_VALUE) continue;  // amount 값이 없는 경우 도달하지 않은 것이므로 이 경우는 따지지 말아야 한다.
                if(i+coin > amount) continue; //  동전이 음수인 경우는 없으므로 amount를 초과하는 경우에는 amount에 도달할 수 없다.
                if(dp[i+coin] > dp[i]+1) dp[i+coin] = dp[i]+1;
            }
        }
        
        if(dp[amount] == Integer.MAX_VALUE) return -1; // 도달할 수 없는 지점인 경우
        else return dp[amount];
    }
}

교훈점

- DP로 반복되는 연산을 저장한다. (메모이제이션)