[Javascript/PGS] Lv.3 : 거스름돈 (DP)

 

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

프로그래머스

---

프로그래머스 레벨 3

보자마자 dp문제인걸 눈치챘다!!! 우하하

문제 유형을 캐치하는 실력은 확실히 점점 늘어나는 것 같다

 

주의할 점은

1. dp[0] = 1으로 초기화해줘야 함. (0원을 만드는 방법 1가지)

2. 이중 반복문을 돌릴 때, 돈의 단위를 바깥에, 총 액수를 안쪽에 놓고 반복해야 중복이 생기지 않는다. (조합)

이렇게 해야 동전이 하나씩 고려되며, 순서를 바꿔도 같은 결과로 취급함.

반대로 한다면 5원을 만드는 방법이 2+3과 3+2로 두 번 세어질 수 있음 (순열)

 

gpt가 이제 그림도 그려준다 ㅋㅋ 근데 뭔 그림인지 모르겠음

 

나의 풀이

function solution(n, money) {
    var answer = 0;
    let mod = 1000000007;
    // 경우의 수...dp?
    // 금액-a의 경우 + 금액-b의 경우 + 금액-c의 경우 + ...
    let dp = new Array(n+1).fill(0);
    dp[0] = 1;
    
    for (let i = 0; i < money.length; i++) {
        for (let j = money[i]; j <= n; j++) {
            dp[j] += dp[j - money[i]] % mod;
        }
    }
    console.log(dp);
    answer = dp[n];
    return answer;
}