LeetCode 322. Coin Change

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

Coin Change - LeetCode

 

문제 풀이는 다음과 같다.

 

1. 먼저 amount가 0일 경우, 정답은 어차피 0으로 고정되어있다. 이와 관련된 조건문을 맨 위에 적어주자.

        if(amount==0) return 0;

2. amount의 값 만큼 vector<int> sum변수를 1개 생성한다. 이때 중요한 점이, int형 최대값으로 초기화를 해줘야한다.

이 문제에서 요구하는 것은 동전을 가장 적게 쓴 케이스를 구해야하기 때문이다.

동시에 sum[0] = 0으로 초기화해준다.

        vector<int> sum(amount+1,1e9);
        sum[0] = 0;

 

3. 2중 for문을 세운다. 자세한 코드는 아래를 참고한다.

        for(int i=0; i<coins.size(); i++){
            for(int j=coins[i]; j<=amount; j++){
                sum[j] = min(sum[j],1+sum[j-coins[i]]);
            }
        }

예를들어 coin[0] = 2이고 amount의 최대값은 11이었다고 가정하자.

sum[2] = min(sum[2], 1+sum[2-coins[0]]이 될 것이다.

즉, 현재 sum[2]의 값인 1e9 vs 1 ( 1(현재 새롭게 동전을 한 번 쓰게된 값)+ 0 (sum[2-coins[0]] = sum[0]) ), 이 둘 중 최소값이 들어가게 된다.

 

이렇게 coins의 마지막값까지 for문을 돌려 가장 최소값으로 해당 값을 구현할 수 있는 갯수만 저장된다.

 

4. 마지막으로 sum[amount]의 값이 1e9라면 불가능한 케이스이니 -1을 출력하고, 그렇지 않을 경우 sum[amount]의 값을 출력한다.

        if(sum[amount]!=1e9) return sum[amount];
        else return -1;

 

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount==0) return 0;
        vector<int> sum(amount+1,1e9);
        sum[0] = 0;
        for(int i=0; i<coins.size(); i++){
            for(int j=coins[i]; j<=amount; j++){
                sum[j] = min(sum[j],1+sum[j-coins[i]]);
            }
        }
        if(sum[amount]!=1e9) return sum[amount];
        else return -1;
    }
};