백준: 2293 동전 1

문제

2293번: 동전 1

 

문제 풀이

 다른 가치를 가진 동전이 주어질 때, 해당 동전들의 합으로 K가 되는 경우의 수를 구하는 문제이다. 문제를 풀기 위해서는 각 동전 별로 금액을 계산할 수 있는 경우의 수를 구하고 이를 메모이제이션을 통해 누적하여 답을 도출할 수 있다.

 

 위와 같이 동전의 가치에 따라 발생할 수 있는 경우의 수를 구할 수 있다. 가장 작은 동전으로 구할 수 있는 경우의 수는 금액에 따라 1가지씩만 존재하게 된다. 하지만 그 다음으로 큰 가치의 동전에 대한 경우의 수를 계산하기 위해서는 이전에 구한 경우의 수를 합산해주어야 된다.

 

 예를 들어, 동전의 가치가 2일 때 3을 구할 수 있는 경우의 수는 3 - 2는 1이 되므로 1을 구할 수 있는 경우의 수이다. 또한 동전의 가치가 4일 때 4를 구할 수 있는 경우의 수는 4 -2, 2를 구할 수 있는 경우의 수는 1일 때 한가지, 2일 때 한가지 이므로 총 2가지가 된다. 이런 식으로 모든 동전 가치에 대한 값을 누적하여 위의 Total과 같이 K에 대한 경우의 수를 찾을 수 있다.

 

from sys import stdin


if __name__ == "__main__":
    n, k = map(int, stdin.readline().split())
    coins = [int(stdin.readline()) for _ in range(n)]
    dp = [1] + [0] * k

    for coin in coins:
        for price in range(coin, k + 1):
            if price >= coin:
                dp[price] += dp[price - coin]

    print(dp[k])