[백준 2293번] 동전 1 (python)

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

기록

(dp 8일차) 코드 더 짧고 간단하게 하고 싶어서 두 번 제출했다.

 

이 문제는 동전들의 조합을 세야되는 문제이기 때문에 coin 순서대로 경우의 수를 계산했다. n원의 동전 조합의 경우의 수를 저장하는 dp배열을 사용하여, coin 별로 dp[n]+=dp[n-coin]을 계산하여 저장했다.

 

코드

from sys import stdin

n, k = map(int, stdin.readline().split())
dp = [0]*(k+1)
dp[0] = 1
for _ in range(n):
    coin = int(stdin.readline())
    for i in range(coin, k+1):
        dp[i]+=dp[i-coin]

print(dp[k])

1. n원의 동전 조합의 개수를 저장하는 dp배열 생성하여 0일 때 1로 초기화한다.

2. 각 동전 순서대로 만들 수 있는 동전의 경우의 수를 갱신한다.

3. k원의 동전 조합 개수를 출력한다.