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

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 해주세요.

 

나의 시도

n의 크기가와 화폐 단위가 크기 때문에 DFS, BFS 등을 이용한 완전 탐색의 가능성을 배제시켰다.

또, 특정 수 k 로 나눈 나머지를 return 하라는 제한사항을 보고 DP로의 접근을 시도하였다.

 

내가 가장 먼저 시도한 방법은 m종류의 화폐를 이용해 n의 금액을 만들 수 있는 방법을 기억하는 2차원 DP를 만드는 것이었다.

문제에서 주어진 예시로 생성되는 2차원 DP는 다음과 같다.

	1원을 만드는 방법	2원을 만드는 방법	3원을 만드는 방법	4원을 만드는 방법	5원을 만드는 방법
1원까지 사용	1	1	1	1	1
2원까지 사용	1	2	2	3	3
5원까지 사용	1	2	2	3	4

 

k개의 화페를 이용해 n원을 만들기 위해 k번째 화폐를 사용하는 경우와 사용하지 않는 경우가 존재한다. 이 때 k번째 화폐는 중복하여 사용할 수 있기 때문에 k번째 화폐 (money[k] 원)을 사용하여 n원을 만드는 방법은 다음과 같이 구할 수 있다.

k-1번째 화폐를 사용해 n원을 만드는 방법 + .... + k-1번째 화폐를 사용해 n-(money[k] * j) 

이때의 j = money[k] * j < n을 만족하는 최대 정수

즉, 2원을 사용해 5원을 만드는 방법은 1원을 사용해 1원을 만드는 방법 + 1원을 사용해 3원을 만드는 방법 + 1원을 사용해

5원을 만드는 방법이다.

그러나, 이 방법을 이용해 문제를 해결하면 시간 초과가 발생한다.

 

정답 설명

문제를 해결하기 위해서는 더 적은 수의 연산이 필요했다.

그 해결 방법은 1차원 DP 배열을 사용하는 것이었다.

 

DP에서 저장하는 값은 다음과 같다.

(k번째 갱신 시)

DP[i] = k번째 화폐까지를 사용해 i원을 만드는 방법

즉, 위에서 만들었던 DP를 1차원으로 축소시킨 모양이다.

이 때 i번째 원소의 값을 구하는 방법은 다음과 같다.

 

k번째 화폐를 이용해서 n원을 만드는 방법은 k번째 화폐를 사용해 n-money[k]원을 만드는 방법과 k번째 화폐를 사용하지 않고 n-money[k]원을 만드는 방법으로 구분된다. ( 각각의 n-money[k]를 만드는 방법에서 k번째 화폐를 한번만 사용하면 우리가 찾는 k번째 화폐를 이용해 n원을 만드는 경우의 수를 구할 수 있다.) 

 

또, 세 정수 A, B, C에 대해 (A + B) % C == ((A%C) + (B%C)) % C를 만족하기 때문에 DP의 값을 업데이트하는 과정에서 DP의 값을 1,000,007로 나눈 나머지를 저장해 주면 된다. 이는 덧셈, 뺄셈, 곱셈에 대해 mod 연산에 분배법칙이 적용되기 때문이다.

 

소스 코드

import java.util.*;
class Solution {
    
    public int solution(int n, int[] money) { 
        int answer = 0; 
        int[] DP = new int[n+1];
        Arrays.sort(money);
        
        DP[0] = 1;
        for(int i = 0; i<money.length; i++){ //i번째 돈까지를 이용해
            for(int j = 0; j<=n; j++){//j번째 돈을 만드는 방법
                if(j - money[i] >= 0)
                    DP[j] += DP[j-money[i]];
                    DP[j] %= 1000000007;
            }
        }
        
        return DP[n];
    }
}