Coin Combinations I

https://cses.fi/problemset/task/1635

CSES - Coin Combinations I

오늘 문제는 동전 액면 집합이 주어질 때 목적한 금액(x)을 만들기 위한 동전 순열의 가지수(dp(x)라 부르자)를 구하는 것이다. 문제에선 조합이라고 했지만 같은 동전 조합의 순서가 다른 경우를 따로 센다.

발상만 정하면 쉽다. 만일 동전 액면 집합 coins = {2,3,5} 에 대해 11을 만들려고 하면, 2, 3, 5를 맨 나중 고른 경우가 모두 상이한 조합이 될 것이며, 이를 제외한 목표값에 대한 부분문제로 recurse 할 수 있다. 그러면 dp(11)은,

dp(11) = dp(11-2) + dp(11-3) + dp(11-5) 가 된다.

이를 코드로 짜면

# Coin Combinations I
import sys
sys.stdin = open("test_input.txt", "r")
n, x = map(int, input().split())  # the number of coins and the desired sum of money.
coins = list(map(int, input().split()))
MOD = 10**9 + 7
dp = [1] + [0] * x
for i in range(1, x + 1):
    for c in coins:
        if i - c >= 0:
            dp[i] += dp[i - c]
            dp[i] %= MOD
print(dp[x])

이렇게 될 것이다.

보통 큰 수의 경우는 특정 수로 나눈 나머지를 결과값으로 저장하도록 요구되는 것이 일반적인데, 각 부분문제에 대한 가지수를 더할 때마다 나머지로 덮어쓰면 된다. 그렇게 해도 되는 이유는 다음 식 때문이다.

(a + b) mod m = (a mod m + b mod m) mod m

 

참고로, 맨 위의 두 줄은 파일에 저장된 값을 불러와서 입력값으로 가져올 때 사용하는 것으로, 입력을 직접 받을때는 지우고 실행하면 된다.