boj.kr/2293 동전1 (gold5) 파이썬 풀이

1. dp를 목표금액 길이만큼 0으로 초기화

2. dp[0]을 1로 초기화 (코인 1개를 사용하는 경우)

3. coins를 순회하면서 아래를 반복

3.1. 현재 코인금액부터 목표금액까지 순회하면서 순회하는 인덱스(i) -현재코인금액(c)이 0이상이면, dp[i] += dp[i-c]

4. dp의 마지막 원소를 출력

 

N, K = map(int, input().split())
coins = []
for _ in range(N):
    coins.append(int(input()))

dp = [0 for _ in range(K+1)]
dp[0] = 1

for c in coins:
    for i in range(c, K+1):
        if i-c >= 0:
            dp[i] += dp[i-c]

print(dp[K])

 

dp[n] 을 n금액을 만드는 모든 경우의 수로 저장할 수 있다.