EunSung.log

거스름돈

4 min read

문제 정보

풀이

가지고 있는 돈(money)을 통해서 거스름돈을 줄 수 있는 모든 경우의 수를 구하는 문제다.

문제의 예시에서 제시된 동전인 1원, 2원, 5원을 통해 n원을 만드는 경우의 수를 살펴보면 다음과 같다.

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

‘1원을 사용한 경우’, ‘2원을 사용한 경우’, ‘5원을 사용한 경우’가 누적되면서 전체 경우의 수가 만들어지는 것을 확인할 수 있다. 이러한 상향식 구조 때문에 DP를 사용해 해결할 수 있다.

여기서 DP[n]을 주어진 금액으로 n원을 만드는 경우의 수라고 정의한다.

먼저 1원만 사용했을 때 각 경우는 다음과 같다.

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

여기서 2원을 추가로 사용하면 각 경우는 다음처럼 업데이트된다.

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

이때, 추가된 각 경우의 수는 모두 마지막에 2원을 더한 경우라는 공통점이 있다.

예를 들어, DP[3]을 살펴보면,

  • 기존의 경우의 수 (1원만 사용한 경우)
  • 2원을 추가로 사용함으로써 새로 생긴 경우의 수

이 두 종류가 합쳐져 DP[3]이 된다.

여기서 ‘2원을 마지막으로 더하는 경우의 수’는 DP[3 - 2] = DP[1]과 동일하다.

왜나하면, 1원(= 3원 - 2원)을 만드는 모든 방법에 2원을 더하면 모두 3원을 만드는 경우가 되는 것이기 때문이다.

즉, DP[3]은

  • 기존의 3원을 만드는 경우의 수: (업데이트 전) DP[3]
  • 2원을 사용함으로써 새로 생긴 경우의 수: DP[3 - 2] = DP[1] 으로 이루어진다.

이를 일반화하면 DP[n] = DP[n] + DP[n - m]이라는 점화식이 나온다.

  • DP[n]: 이전 금액들로 만든 기존 경우의 수
  • DP[n - m]: m원을 마지막에 사용함으로써 새로 생기는 경우의 수

코드

import java.util.*;
 
class Solution {
	public int solution(int n, int[] money) {		
		int[] dp = new int[n + 1];
		dp[0] = 1;
		
		for (int i = 0; i < money.length; i++) {
			for (int j = money[i]; j <= n; j++) {
				dp[j] += dp[j - money[i]];
				dp[j] %= (int) 1e9 + 7;
			}
		}
		
		return dp[n];
	}
}

백링크