프로그래머스 12907 거스름돈 자바스크립트 풀이

난이도 : Lv. 3

풀이일 : 2412275

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

프로그래머스

---

문제

---

아이디어

• 각 동전에 대해 해당 동전의 가격부터 궁금한 금액까지 해당 동전으로 만들 수 있는 개수 추가

---

코드

function solution(n, money) {
    var answer = 0
    var dp = new Array(n + 1).fill(0)
    dp[0] = 1
    
    for (coin of money) {
        for (let i = coin; i < n + 1; i++) {
            dp[i] += dp[i - coin]
        }
    }
    answer = dp[n] % 1000000007
    
    return answer
}

• dp 배열은 구해야할 수까지 생성하기 위해 n+1
• 0원을 만들 수 있는 경우의 수 1 기록
• 각 동전에 대해 반복하며 해당 동전부터 n값까지 동전을 사용해 만들 수 있는 개수 기록
• 답이 너무 커질 경우 처리를 위해 문제 요구사항 수로 나누어 answer 기록 및 반환

---

제출 결과