[백준 파이썬] 2293 동전 1

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

2293번: 동전 1

 

문제

 

주어진 동전을 합해서 원하는 숫자를 만드는 경우의 수를 구하는 문제이다.

---

풀이

경우의 수를 구해야 하기 때문에 Dp를 사용하여 해결하였다.

 

1차원 배열에 동전마다 가능한 경우의 수를 누적하면서 구하는 방식으로 해결하였다.

 

DP[N]은 N을 만들기 위해 필요한 경우의 수이다.

예를들어 1로만 이루어진 동전으로 1~N개의 숫자를 만드는 경우의수를 구할 때

DP[1] ~ DP[N] 값은 모두 1이 된다. 

1 = 1

1 + 1 = 2

1 + 1 + 1 = 3

이렇게 경우의 수가 한가지만 나오기 때문이다.

 

이 방식을 이용해서 DP값을 누적해주면 된다

for c in coins:
    for i in range(c, k + 1):
        DP[i] += DP[i - c]

만약 1, 2로 구성된 동전에서 DP[3]을 구하기 위해서는 

기존 1로만 이루어진 DP[3] = 1에서 1, 2 동전 두개로 구성하기 위해

DP[3] = DP[3](기존) + DP[3 - 2] (기존 DP[1]에서 2동전을 추가한 경우) 이다.

 

해당 방법을 동전의 종류만큼 반복하면 모든 경우의 수를 구할 수 있게된다.

 

 

코드

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

coins = []
for i in range(n):
    coins.append(int(input()))
coins.sort()

DP = [0] * (k + 1)
DP[0] = 1
for c in coins:
    for i in range(c, k + 1):
        DP[i] += DP[i - c]
print(DP[k])