[알고리즘] 백준 - 2293. 동전1

1. 문제

동전1

2. 접근

- 이 문제는 이코테의 효율적인 화폐 구성과 유사하다. N가지의 화폐로 K원을 만족시키는 경우의 수를 구하는 DP 문제임을 알 수 있다

- 각 숫자를 (1,2,5)를 더해서 숫자를 나타내는 방법을 표로 경우의 수를 확인할 수 있다.

경우의수

 

3. 풀이

# 골드5 - 2293
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coin = []
for i in range(n):
    coin.append(int(input()))

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

for i in coin:
    for j in range(1, k+1):
        if j - i >= 0:
            d[j] += d[j-i]

print(d[k])