프로그래머스 LEVEL 3(거스름돈)

사용 언어 : javascript
해결 날짜 : 2022-12-30
해결 방법 :
- dp를 활용해 문제 해결
  - dp[0]은 1로 초기화
  - dp의 i번째 인덱스에 저장될 값은 i원으로 만들 수 있는 money 방법의 수
  - 현재 i번째 인덱스에서 m원 전의 dp값을 더한 값을 dp에 업데이트
  - 즉, dp[i] += dp[i - m]
    - 문제의 테스트 케이스를 예로 들었을 때, 2의 경우
      - 2원을 이용해 2원을 표현할 경우 2원를 1번 사용하면 된다. 즉, dp[2] = dp[2] + dp[0]
      - 2원을 이용해 4원을 표현할 경우 2원을 2번 사용하면 된다. 즉, dp[4] = dp[4] + dp[2]
      - 2원을 이용해 6원을 표현할 경우 2원을 3번 사용하면 된다. 즉, dp[6] = dp[6] + dp[4]
    - 다시 말해 변화 전 경우의 수에 m원만큼 작은 경우의 수를 더하면 구할 수 있다.
회고 :
- 처음에 보자마자 dp문제라고 생각은 했는데 2차원 배열을 써야하냐? 고민을 했다.
- 풀고 나서 보니 기본적인 dp 동전 거스름돈 문제와 크게 차이나지는 않는 것 같아 dp를 더 공부해야겠다.

코드

function solution(n, money) {
  const dp = Array.from({ length: n + 1 }, () => 0);
  dp[0] = 1;

  for (const m of money) {
    for (let i = m; i < n + 1; i++) {
      dp[i] += dp[i - m];
    }
  }

  return dp[n] % 1000000007;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges