[백준] 2293번 : 동전 1

https://www.acmicpc.net/problem/2293

2293번: 동전 1

테스트 케이스인 1,2,5를 예를 들어 문제를 풀어보겠습니다.

n = 3이고 k=10인 문제에서, k=10이기때문에 10일때 1,2,5 동전으로 만들 수 있는 경우의수를 구해야한다. 우선 10까지 구하는 방법을 나열해본다.

동전 1)

- 1일때 : 1

- 2일때 : 11

- 3일때 : 111

- 4일때 : 1111

- 5일때 : 11111

- 6일때 : 111111

- 7일때 : 1111111

- 8일때 : 11111111

- 9일때 : 111111111

- 10일때 : 111111111

 

동전 2)

- 1일때 : 1

- 2일때 : 11, 2

- 3일때 : 111, 12

- 4일때 : 1111, 112, 22

- 5일때 : 11111, 1112, 122

- 6일때 : 111111, 11112, 1122, 222

- 7일때 : 1111111, 111112, 11122, 1222

- 8일때 : 11111111, 1111112, 111122, 11222, 2222

- 9일때 : 111111111, 11111112, 11111122, 111222, 12222

- 10일때 : 1111111111, 111111112, 1111111122, 1111222, 112222, 22222

 

동전 5)

- 1일때 : 1

- 2일때 : 11, 2

- 3일때 : 111, 12

- 4일때 : 1111, 112, 22

- 5일때 : 11111, 1112, 122, 5

- 6일때 : 111111, 11112, 1122, 222, 15

- 7일때 : 1111111,111112,11122, 1222, 115, 25

- 8일때 : 11111111, 1111112, 111122, 11222, 2222, 1115, 125

- 9일때 : 111111111, 11111112, 11111122, 111222, 12222, 11115, 1125, 225

- 10일때 : 1111111111, 111111112, 1111111122, 1111222, 112222, 22222, 111115, 11125, 1225, 55

 

즉, 코인을 순회하면서 dp테이블을 dp[i-coin] 값을 추가로 더해준다면 아래의 결과를 얻을 수 있다.

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

dp[0] = 1
for c in coin:
    for i in range(k+1):
        if i - c >= 0:
            dp[i] += dp[i-c]

print(dp[k])