[프로그래머스/Level3] 거스름돈 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• DP

dp[ j ] : 금액 j를 낼 수 있는 방법 수 (dp[n - 화폐 종류1], dp[n - 화폐 종류2], ...)
⇒ dp[ j ] = dp[ j - money[i] ]

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static final int MOD = 1_000_000_007;
    
    public int solution(int n, int[] money) {
        Arrays.sort(money);
        
        int[] dp = new int[n + 1];
        dp[0] = 1; // 화폐 하나로만 거스름돈을 채울 수 있는 경우
        
        for(int i = 0 ; i < money.length ; i++) {
            for(int j = money[i] ; j <= n ; j++) { // 화폐 이전까지는 값이 동일하므로 갱신할 필요 X
                dp[j] += dp[j - money[i]] % MOD;    // 💥 화폐 이전까지의 합 + 새 화폐로 낼 수 있는 방법
            }
        }
                
        return dp[n];
    }
}

 

 

 

 

➕ 다른 풀이 방식

2차원 dp를 활용한 풀이

[프로그래머스] 거스름돈 / Java

 

---

💦 어려웠던 점

- DP인 거는 알았는데 점화식을 찾지 못했다,,허허허허

- 이전까지의 합이 모두 같으니까 굳이 채울 필요가 없어서 1차원으로 해결하는 아이디어 갓챠,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고.. 나도 dp 풀 때 이렇게 식을 그려서 진행해봐야겠다,,,

[프로그래머스 level_3] 거스름돈 for JAVA

 

프로그래머스 거스름돈(Java, LV3) /DP

 

[JAVA/DP] 프로그래머스 거스름돈