백준 2293번: 동전 1 (Python)

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

해설

얼핏 보면 그리디를 활용하는 것처럼 보일수도 있지만 다이나믹 프로그래밍을 활용한 문제이다. 상위 가치의 동전이 하위 가치의 동전들의 합으로 구성될 수 있기 떄문이다. (1원, 5원이 있을 경우 1원x5개로 구성 가능)

 

동전들을 조합해 k원의 가치를 만드는 경우의 수를 모두 구해야 한다. 따라서 DP[n]은 'n원의 가치를 만들 수 있는 모든 경우의 수'가 된다. 동전 DP 문제는 표를 그려보면 쉽게 이해할 수 있다.

 

아래는 n = 3, k = 10, coin = [1,2,5] 인 경우에 대한 DP 표를 구성한 결과다.

실제로 0원짜리 동전은 없지만 있다고 가정해보자.

0원 동전으로 만들 수 있는 가치는 존재하지 않음으로, 모든 경우의 수가 0이 된다.

 

1원짜리 동전이 추가되면 어떨까?

1원 가치는 1, 2원 가치는 1+1, 3원 가치는 1+1+1.. 이런식으로 표현할 수 있으니

모든 k원에 대해 1가지 경우의 수가 생겨날 것이다.

이번에는 2원짜리 동전이 추가되었다.

여기서부터 머리를 좀 써야한다. 우리는 이미 0원, 1원짜리 동전만으로 만들 수 있는 경우의 수를 정확히 알고 있다.

그렇다면, 이미 확정된 경우의 수를 기본으로 숫자를 더해나가면 되지 않을까?

 

2원 가치를 만드는 모든 경우의 수는, 0원 가치를 만드는 경우(1)에 기존 경우 (1)를 더한 값 2이다.

3원 가치를 만드는 모든 경우의 수는, 1원 가치를 만드는 경우(1)에 기존 경우 (1)를 더한 값 2이다.

4원 가치를 만드는 모든 경우의 수는, 2원 가치를 만드는 경우(2)에 기존 경우 (1)를 더한 값 3이다.

...

(k+coin)원 가치를 만드는 경우의 수는 k원 가치를 만드는 경우의 수를 더한 값으로 갱신해주면 된다.

 

5원짜리 동전이 추가된 경우는 위와 같다.

이러한 이해를 바탕으로 DP 배열을 업데이트 해나가면 된다.

코드

n, k = map(int, input().split())
coins = []

for i in range(n):
    coins.append(int(input()))
coins = sorted(coins)
# 가치가 작은 순부터 정렬

DP = [0] * (k+1)
DP[0] = 0

for coin in coins:
    for i in range(k+1):
        if DP[i] == 0:
            if i % coin == 0:
                DP[i] = 1
            continue

        if i != 0:
            DP[0] = 1

        if i + coin <= k:
            DP[i+coin] += DP[i]

print(DP[k])