[BOJ] 2293 - 동전 1 (Python)

 

 

아이디어

 

동적 계획법으로 경우의 수를 더해 나간다.

 

 

풀이

 

가치 합을 인덱스로 하여 경우의 수를 저장하는 리스트 dp를 생성한다.

k보다 큰 값은 고려할 필요가 없으므로 dp의 길이는 k+1로 하고, 인덱스 0의 값은 1, 나머지는 0으로 채운다.

인덱스 0의 값을 1로 채우는 이유는 이후 for문에서 동전 가치의 경우의 수를 증가시키기 위함이다.

 

차례로 입력 받은 동전의 가치 c로 c보다 더 작은 가치는 만들 수 없으므로 for문에서 가치 합을 c부터 시작한다.

c 이상의 가치 합 j의 경우의 수 dp[j]에 j에서 c를 뺀 가치의 경우의 수 dp[j-c]를 더해 나간다.

 

import sys

input = sys.stdin.readline

def solution():
    n, k = map(int, input().split())
    dp = [1]+[0]*k
    for i in range(n):
        c = int(input())
        for j in range(c, k+1):
            dp[j] += dp[j-c]
    print(dp[k])

solution()