[백준 2293] 코인1 (Python)

문제

 

코드

n, k = map(int, input().split())

coin = []

for i in range(n):
    coin.append(int(input()))
sum = [0 for i in range(k+1)]
sum[0] = 1

for i in coin:
    for j in range(i, k+1):
        sum[j] += sum[j-i]

print(sum[k])

예제의 경우로 설명해보면, 동전 1만 선택했을 경우, 동전 1, 2원 중에서 선택한 경우, 동전 1, 2, 5원 중에서 선택한 경우를 차례로 구한다.

 

sum[0]에 1을 넣어준 이유는 j원이 되는데 i원 1개만 선택해도 되는 경우를 고려한것입니다. (j == i인 경우)

sum[j] += sum[j-i] 코드는 동전 i원을 뺀 값이 되는 경우에 i원 동전을 고르는 경우를 더하는것입니다.

 

 

 

 

너무 어렵다... 생각해 내질 못하겠어서 결국 구글링을했다 ㅜㅜㅜ

 

 

 

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

2293번: 동전 1