[programmers] Lv3 거스름돈 - Python & Java

https://school.programmers.co.kr/learn/courses/30/lessons/12907

프로그래머스

 

 

 

<문제 풀이>

- DP를 이용하는 문제인 것 같다.

- 해당 문제는 앞서 포스팅한 백준의 동전 문제들과 유사? 가 아니라 그냥 같은 것 같다.

https://kcw0360.tistory.com/4

[BAEKJOON] 9084 동전 - Python

https://kcw0360.tistory.com/35

[BAEKJOON] 2293 동전 1 - Python

 

 

 

<Code>

def solution(n, money):
    dp = [1] + [0] * n

    for coin in money:    # 돈의 종류 순서대로 탐색
        for i in range(coin, n+1):    # coin(돈의 종류)으로 i원을 만들수 있는 방법은 i-coin 금액에 해당하는 방법의 수와 같다.
            dp[i] += dp[i-coin]

    return dp[n]

class Solution {
    public int solution(int n, int[] money) {
        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int coin : money) {
            for (int i = coin; i < n+1; i++) {
                dp[i] += dp[i-coin];
            }
        }

        return dp[n];
    }
}

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.