[Java] 프로그래머스 level3 거스름돈

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

프로그래머스

코딩테스트 연습 > 연습문제 > 거스름돈

 

문제 설명

Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.

예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다.

1원을 5개 사용해서 거슬러 준다.
1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
5원을 1개 사용해서 거슬러 준다.

거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세요.

 

제한 사항

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

 

문제 접근

제한 사항을 보면 1,000,000,007 나눈 나머지를 return 하라고 했다. 

먼저 1,000,000,007 static final 변수로 지정 DP를 하면서 + 연산을 하면 나머지 처리를 해줄 것이다.

 

N = 5  MONEY[1, 2, 5] RESULT: 4

1 : 1

2 : 1 + 1 , 2

3 : 1 + 1 + 1 ,  2 + 1

4 : 1 + 1 + 1 + 1, 2 + 1 + 1, 2 + 2

5 : 1 + 1 + 1 + 1 + 1 , 2 + 1 + 1 + 1 , 2 + 2 + 1, 5

 

2중 for문으로 DP를 채운다.

아마 이 문제를 처음 푸는 사람이거나 막히는 사람이면  대부분 첫 번째 for문을 1 ~ n으로 잡을 것이다. 

나 또한 처음에 그렇게 풀었다. 하지만 그런식으로 for문을 돌리면 중복이 생겨서 원하는 값을 찾기 어렵다. 

 

ex) 1 + 1 + 2 == 1 + 2 + 1 == 2 + 1 + 1   ( 3가지의 경우의 수가 아닌 1가지이다. )

 

첫 번째 for문을 기준을 money로 잡는다. 

두 번째 for문의 기준을 1 ~ n 으로 잡는다. 

 

이렇게 풀면 왜 정답이 나오는지 한번 돌려보자

 

N = 5  MONEY[1, 2, 5] RESULT: 4 

DP[money]++;
for(int j = 1 <= n; j++){  
     if(j - money >= 0)          // j-money가 0보다 작으면 ArraysBoundException이 발생한다. 예외 처리를 하자.
     DP[j] += DP[j - money];
}

 

DP[0] = 0 DP[1] = 0  DP[2] = 0  DP[3] = 0  DP[4] = 0  DP[5] = 0 

 

money : 1 

 

DP[1] = 1

DP[1] = 1 DP[2] = 1 DP[3] = 1 DP[4] = 1 DP[5] = 1 

 

money : 2 

DP[2] = 2

DP[2] = 2 DP[3] = 2 DP[4] = 3 DP[5] = 3

 

money : 5 

DP[5] = 4

 

Result : 4 

 

정리 

2중 for문을 돌면서 DP[i] += DP[i - money] 의 경우의 수를 누적해서 돌리면 정답이 나온다. 

정답 코드

class Solution {
    static final long INF = 1000000007;
    public long solution(int n, int[] money) {
        int size = money.length;
        long [] DP = new long[n+1];
        for(int i = 0; i < size; i++){
            int cur = money[i];
            if(cur > n) continue;
            DP[cur]++;
            for(int j = 1; j <= n; j++){
                if(j - cur >= 0){
                    DP[j] += DP[j-cur];
                    DP[j] %= INF;
                }
            }
        }
        return DP[n];
    }
}