[JS] 거스름돈

문제

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

프로그래머스

 

풀이

이 문제는 돈의 조합으로 나올 수 있는 금액들의 DP를 이용해 풀이해야한다.

 

생각보다 구현 아이디어가 팍 하고 떠오르지 않았다.

 

코드

function solution(n, money) {
  const dp = Array.from({ length: n + 1 }, () => 0);
  dp[0] = 1;
    
  for (const coin of money) {
    for (let i = coin; i < n + 1; i++) {
      dp[i] += dp[i - coin];
    }
    console.log(dp)
  }
  return dp[n] % 1000000007;
}