23.08.11. 풀었던 문제들 복기

Leetcode 518. Coin Change II, 25분

 백준 2293. 동전 1과 동일한 문제.

 일단 2차원 dp로 푼다고 하면, dp[i][j] : coin i까지 봤을 때 j원을 표기할 수 있는 개수로 두자.

• i번째 coin을 안쓰는 경우 - dp[i][j] = dp[i-1][j]
• i번째 coin을 쓰는 경우   - dp[i][j] = dp[i][j-coin[i-1]]

위와 같이 되므로 이 점화식을 그대로 적용하기만 하면 된다.

 

 space complexity를 조금 개선할 수 있는데, dp[i][j] = dp[i-1][j]는 항상 고정이므로 dp를 1차원 배열로 만들수도 있다.

// time O(nm), space O(nm)
// Runtime 43 ms Beats 39.13%
// Memory 18.4 MB Beats 58.93%

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<vector<int>> dp(coins.size(), vector<int>(amount+1, 0));
        for(int i = 0; i<coins.size(); i++){
            dp[i][0] = 1;
            for(int j = 1; j<=amount; j++){
                if(i-1 >= 0) dp[i][j] = dp[i-1][j];
                if(j - coins[i] >= 0) dp[i][j] += dp[i][j-coins[i]];
            }
        }

        

        return dp[coins.size()-1][amount];
    }
};

// time O(nm) space O(m)
// Runtime 13 ms Beats 76.84%
// Memory 7.1 MB Beats 90.15%
class Solution {
public:
    int change(int amount, vector<int>& coins) {


        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for(int i = 0; i<coins.size(); i++){
            for(int j = 1; j<=amount; j++){
                if(j - coins[i] >= 0) dp[j] += dp[j-coins[i]];
            }
        }

        return dp[amount];
    }
};