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

문제

거스름돈
https://school.programmers.co.kr/learn/courses/30/lessons/12907
 

 

풀이

설명

n원을 거슬러 줄 방법의 수를 구하는 문제입니다.
 
dp를 사용해 해결할 수 있습니다.
 
dp[i]는 i원을 거슬러 주는 방법의 수를 의미합니다.
dp[0] = 1로 초기화합니다.
 
각 화폐 단위에 대해서 그 화폐 단위까지 도달하는 방법의 수를 누적해 계산합니다.
 
점화식은 다음과 같습니다.
dp[i] = dp[i] + dp[i - coin]

 

예시 코드

function solution(n, money) {
  const MOD = 1000000007;

  const dp = Array(n + 1).fill(0);
  dp[0] = 1;

  for (const coin of money) {
    for (let j = coin; j <= n; j++) {
      dp[j] = (dp[j] + dp[j - coin]) % MOD;
    }
  }

  return dp[n];
}