백준 알고리즘 23단계 동적 계획법 2- 동전1(2293번) Python

이번에 풀 문제는 동전 1 이다.

해당 문제에 대한 링크는 아래와 같다.

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

2293번: 동전 1

 

1. 문제 확인

 

2. 문제 풀이

 

각각의 경우의 수에서 중복된 경우의 수를 생각하는 경우였다.

예를 들면 4의 경우의 수는 
4점을 만들기 위해 2점까리 동전을 사용하였을 때, 4-2를 하면 2가 나온다.
이때 나오는 2의 경우는 2이므로 2를 적어주는 논리이다.

 

from sys import stdin


n, k = map(int, stdin.readline().split())

coin = []

for _ in range(n):
    coin.append(int(stdin.readline()))

count_list = [0] * (k + 1)
# x원짜리 동전 하나로 x원을 만드는 경우의 수 = 1
count_list[0] = 1

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

print(count_list[k])