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

[DP]-거스름돈

프로그래머스

 

문제 설명

거슬러 줘야 하는 금액 n과 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n원을 거슬러 줄 방법의 수 return

 

[제한 사항]

• n은 100,000 이하의 자연수
• 화폐 단위는 100종류 이하
• 모든 화폐는 무한하게 있다고 가정
• 정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지 return

 

입출력 예시

n	money	result
5	[1,2,5]	4

 

풀이 방법

DP 배열 설정을 잘 해주어야 쉽게 풀 수 있는 문제임..

DP = i원 거스름돈을 받을 수 있는 횟수

 

위의 예시를 사용해서 Bottom-Up으로 구해보면,

1) 거스름돈 0은 아무것도 거슬러 주지 않는 것으로 1로 채우기

0원	1원	2원	3원	4원	5원
1	0	0	0	0	0

 

2) 1원을 이용해서 1원~5원 거슬러 줄 수 있는 경우의 수 구하면,

1원 = 1, 2원 = 1+1, 3원 = 1+1+1, 4원 = 1+1+1+1, 5원 = 1+1+1+1+1 ▶︎ 모두 1개씩 존재

0원	1원	2원	3원	4원	5원
1	1	1	1	1	1

 

3) 2원을 이용해서 2~5원 거슬러 줄 수 있는 경우의 수 구하면,

2원 = 0+2/1+1, 3원 = 1+2/1+1+1, 4원 = 2+2/2+1+1/1+1+1+1, 5원 = 1+2+2/1+1+1+2/1+1+1+1+1

0원	1원	2원	3원	4원	5원
1	1	1+1=2	1+1=2	1+2=3	1+2=3

 

4) 5원을 이용해서 5원 거슬러 줄 수 있는 경우의 수 구하면,

5원 = 5/1+2+2/1+1+1+2/1+1+1+1+1

0원	1원	2원	3원	4원	5원
1	1	2	2	3	3+1=4

 

여기서 규칙이 발생함

DP[i] = DP[i] + DP[i-화폐]

즉, Bottom-Up 방식으로 거슬러 줄 수 있는 경우의 수 합계 구할 수 있음

코드

function solution(n, money) {
    const DIV = 1000000007; // 나눌 수
    
    // 거스름돈 DP 배열: DP[거스름돈] = 거스름돈을 거슬러 줄 수 있는 경우의 수
    const dp = Array.from({length: n+1}, () => 0);
    dp[0] = 1; // 아무것도 거슬러 주지 않는 경우의 수인 1 넣기
    
    for(const m of money) {
        for(let c=m; c<=n; c++) {
            dp[c] += (dp[c-m]%DIV); // DP 규칙 적용
        }
    }
    
    return dp[n];
}

---

참고 사이트

https://review-answer.tistory.com/27

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