프로그래머스 [Lv. 3] 거스름돈 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12907?language=javascript

프로그래머스

정답 코드

function solution (n, money) {
    const MOD = 1000000007;  // 결과를 나누는 모듈러 값 (큰 수 계산 시 오버플로우 방지)
    const dp = Array(n+1).fill().map(() => 0);  // 길이가 n+1인 배열 dp를 0으로 초기화
    dp[0] = 1;  // dp[0]은 1로 설정 (금액 0을 만들 수 있는 경우는 아무 동전도 사용하지 않는 1가지 경우)

    for(let m of money){  // 각 동전 m에 대해 반복
        for(let i = m; i < n+1; i++){  // m부터 n까지 반복
            dp[i] = (dp[i] + dp[i - m]) % MOD;  // 현재 금액 i를 만들 수 있는 경우의 수를 업데이트
        };
    };
    
    const answer = dp[n]; // dp[n]에 저장된 값 (주어진 금액 n을 만들 수 있는 경우의 수)을 answer에 치환
    return answer;
}

풀이 방법

 

1. 기본 설정
   1. MOD = 1000000007은 결과를 큰 수로 나눠서 계산하기 위해 사용한다. 
   2. dp 배열은 n+1 크기로 만들어지며, 모든 값을 0으로 초기화한다. dp[i]는 금액 i를 만들 수 있는 경우의 수를 저장한다.
   3. dp[0]은 1로 설정되는데, 이는 금액 0을 만들 수 있는 경우가 아무 동전도 사용하지 않는 한 가지 경우임을 의미한다.
2. 동전 종류별 경우의 수 계산
   1. 각 동전 m에 대해, 금액 m부터 n까지 반복하며 dp 배열을 업데이트한다.
   2. dp[i]를 dp[i - m]을 더한 값으로 업데이트합니다. 이는 금액 i를 만들기 위해 동전 m을 추가하는 경우의 수를 의미한다.
   3. 이렇게 하면 모든 동전 조합을 고려하게 되며, dp 배열은 각 금액을 만들 수 있는 모든 경우의 수를 저장하게 된다.
3. 결과 반환
   1. 최종적으로 dp[n]에는 주어진 금액 n을 만들 수 있는 경우의 수가 저장되어 있으며, 이 값을 반환한다.

 

 

느낀점

• dp가 어려운 점은 규칙을 찾는 부분이다.
• 규칙 찾는데도 1시간 넘게 걸리는데 dp 문제 나오면 쉽지 않을 것 같다.