February 3, 2023

2293번: 동전 1

문제

• 각각 가치가 다른 n가지 종류의 동전이 주어졌을 때, 동전을 무한히 사용하여 가치의 합을 k원이 되도록 하는 경우의 수
• 1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000
• 시간 제한 0.5초, 메모리 제한 4MB

풀이

from sys import stdin

input = stdin.readline

n, k = map(int, input().split())
coin_list = [int(input()) for _ in range(n)]
dp = [1] + ([0] * k)

for coin in coin_list:
    for j in range(k + 1):
        if (j >= coin):
            dp[j] += dp[j - coin]

print(dp[-1])

• Dynamic Programming 사용
• dp 테이블이 고차원 테이블로 사용 가능하지만, 공간 복잡도가 높음

참고 자료

[백준] 2293 동전1 -파이썬