[Leetcode] 322. Coin Change - DP

1. 문제링크

https://leetcode.com/problems/coin-change/

Coin Change - LeetCode

dp는 동적 계획법인데, 이것은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다

dp를 이해하기 가장 쉬운 문제로는 70. Climbing Stairs가 있다.

 

 

 

2. Key Point

1) coins를 오름차순으로 정렬한다

2) vector<int> dp를 정의하고 size는 amount+1로 설정하고 도달할 수 없는 임의의 값으로 초기화한다(amount+1)

3) 0부터 amount까지의 최소한의 동전갯수를 dp에 업데이트한다

4) dp[amount]가 2에서 설정한 초기값이라면 -1, 그렇지 않으면 dp[amount] 리턴한다

 

 

 

3. 부연설명 추가

coins = [1,2,5], amount = 11일 때

vector<int> dp = {12, 12, 12, 12};가 될 것이고 dp[0]을 0으로 업데이트 한다.

 

그리고나서 이중 for문을 도는데

첫번째 for문은 amount 1 to 11가 될 때 까지 반복하고

두번째 for문은 coins를 돌면서 coins[j] <= i이 될 때 dp를 최솟값으로 업데이트 해준다.

 

dp[0] = 0

dp[1] = min(dp[1], dp[1 - coins[0]] +1) = min(12, dp[0] + 1) = 1;

dp[2] = min(dp[2], dp[2 - coins[0]] + 1) = min(12, dp[1] + 1) = 2;

dp[2] = min(dp[2], dp[2 - coins[1]] + 1) = min(12, dp[0] + 1) = 1;

...

dp[5] = 1;

dp[6] = 2;

...

dp[10] = 2;

dp[11] = 3;

 

 

 

4. 난해한 테스트케이스 추가

coins = [186,419,83,408]
amount = 6249

output : 20 

 

 

 

5. solution

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int maxi = amount+1;
        vector<int>dp(maxi, maxi);
        sort(coins.begin(), coins.end());

        dp[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(int j = 0; j < coins.size(); j++){
                int curr = coins[j];
                if(curr <= i){
                    dp[i] = min(dp[i], dp[i - curr] + 1);
                    cout << "i : " << i << ", curr : " << curr << ", dp updated ! " << dp[i] << endl;
                } else {
                    break;
                }
            }
        }
        return dp[amount] == maxi ? -1 : dp[amount];
    }
};

 

 

6. 위 코드 콘솔출력 결과물 (첫번째 example) 

coins = [1,2,5], amount = 11, output = 3

i : 1, curr : 1, dp updated ! 1
i : 2, curr : 1, dp updated ! 2
i : 2, curr : 2, dp updated ! 1
i : 3, curr : 1, dp updated ! 2
i : 3, curr : 2, dp updated ! 2
i : 4, curr : 1, dp updated ! 3
i : 4, curr : 2, dp updated ! 2
i : 5, curr : 1, dp updated ! 3
i : 5, curr : 2, dp updated ! 3
i : 5, curr : 5, dp updated ! 1
i : 6, curr : 1, dp updated ! 2
i : 6, curr : 2, dp updated ! 2
i : 6, curr : 5, dp updated ! 2
i : 7, curr : 1, dp updated ! 3
i : 7, curr : 2, dp updated ! 2
i : 7, curr : 5, dp updated ! 2
i : 8, curr : 1, dp updated ! 3
i : 8, curr : 2, dp updated ! 3
i : 8, curr : 5, dp updated ! 3
i : 9, curr : 1, dp updated ! 4
i : 9, curr : 2, dp updated ! 3
i : 9, curr : 5, dp updated ! 3
i : 10, curr : 1, dp updated ! 4
i : 10, curr : 2, dp updated ! 4
i : 10, curr : 5, dp updated ! 2
i : 11, curr : 1, dp updated ! 3
i : 11, curr : 2, dp updated ! 3
i : 11, curr : 5, dp updated ! 3