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

 

 

문제 링크

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

프로그래머스

 

 

 

문제

1. 거슬러 줘야 하는 금액 n과 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, n 원을 거슬러 줄 방법의 수를 1,000,000,007로 나눈 나머지 값을 return 하라.
2. n은 100,000 이하의 자연수입니다.
3. money.length ≦ 100

4. 모든 종류의 화폐의 수는 무한하다.

 

 

 

문제 풀이

ex) n = 5, money = [1, 2, 5]

거스름돈	0	1	2	3	4	5
경우의 수	1	1	1	1	1	1

우선 1원을 이용해서 거슬러 줄 수 있는 경우의 수를 계산하면 위와 같다.

거스름돈 0은 무조건 거슬러 줄 수 있다는 의미로 1로 채운다. 

 

거스름돈	0	1	2	3	4	5
경우의 수	1	1	1+1 =2	1+1 = 2	1+2 =3	1+2 = 3

다음으로 2원을 이용하여 거슬러 줄 수 있는 경우의 수를 추가로 계산하면 위와 같다.

거스름돈 2는 1원 2개, 2원 1개를 거슬러 주는 경우로 총 두가지이다. 

거스름돈 3은 1원 3개, 1원 1개와 2원1개 를 거슬러 주는 경우로 총 두가지이다.

거스름돈 4는 1원4개, 1원 2개와 2원 1개, 2원 2개를 거슬러 주는 경우로 총 세가지이다. 

거스름돈 5는 1원5개, 1원 3개와 2원 1개, 1원 1개와 2원 2개를 거슬러 주는 경우로 총 세가지이다. 

 

자세히 보자.
3원을 거슬러 주는 경우를 보면 기존에 1원 3개를 이용하여 거슬러 주는 경우에서 1원 2개를 대신하여 2원 1개를 거슬러 준다. 즉 1원 1개를 사용하는 경우의 수와 동일하다.   

4원을 거슬러 주는 경우를 보면 기존에 1원 4개를 이용하여 거슬러 주는 경우, 또는 1원 2개와 2원 1개를 거슬러주는 경우에서 1원 2개를 2원 1개를 이용하여 거슬러주는 경우의 수와 동일하다. 

 

여기서 규칙이 발생한다.

dp[i] = dp[i]  + dp[i-m(화페)]

 

거스름돈	0	1	2	3	4	5
경우의 수	1	1	2	2	3	4

다음으로 5원을 이용하여 거슬러 줄 수 있는 경우의 수를 추가로 계산하면 위와 같다.

거스름돈 5는 1원5개, 1원 3개와 2원 1개, 1원 1개와 2원 2개, 5원 1개를 거슬러 주는 경우로 총 네가지이다.

 

 

 

 

코드

각 화페를 이용하여 거스름돈을 줄  수 있는 경우의 수를 계산한다.

class Solution {
    final int NUMBER = 1000000007;
    public int solution(int n, int[] money) {
        int[] dp= new int[n+1];
        dp[0]=1;
        for(int m : money){
            for(int i=m;i<=n; i++){
                dp[i] += dp[i-m]%NUMBER;
            }
        }
        return dp[n];
    }
}

 

 

 

 

실행 결과