[백준] 2293: 동전 1(Python)

문제

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

접근 방법

1. DP배열에 동전가치 칸에 경우의수 1개 추가
2. 이전 가치 까지의 경우의 수를 이전 가치 + 현재 가치 칸에 추가해줌

풀이 코드

N, K = map(int,input().split()) # 동전개수, 원하는 가치
coins = sorted(list(int(input()) for _ in range(N))) # 동전 배열
dp = [0] * (K+1) # DP 배열
for coin in coins:
    if coin <= K: # 동전이 원하는 값보다 작을떄만
        dp[coin] += 1
    for i in range(1,K+1):
        dp[i] += dp[i-coin] if i - coin > 0 else 0 # 배열 범위 안이면 더해줌
print(dp[K])