BOJ 2293: 동전 1- 파이썬(Python)

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

<접근 방법>

n가지의 동전을 이용해서 k원을 만들 수 있는 경우의 수를 구하는 문제이다. 문제에서 제시한 예시를 이용하여 분석해보자.

 

초기 상태는 아래의 그림처럼 구성할 수 있을 것이다.

 

우선, 사용 가능한 동전들을 순서대로 사용해서 1부터 시작하여 10까지 진행하는 것을 반복하면 될 것이다. 우선 동전 1일 경우, 모든 k에서 만들 수 있는 경우의 수는 1이 될 것이다. 왜냐하면 각 k는 1을 k개 가지고 있는 것과 같기 때문이다.

 

 

이제 동전 2일 때에는 어떻게 처리해야 할까? 동전 2는 k가 2인 것 부터 시작하면 충분하다. 왜냐하면 2로는 1을 만들 수 없기 때문이다. 현재 k에서 2를 뺀 index에 위치한 값을 더하는 것이다. 이렇게 하면 어떤 수 i에 2를 더하면 k가 되는 경우의 수를 계산할 수 있기 때문이다.

 

이러한 연산을 모든 동전에서 적용하면 아래처럼 구성될 것이다.

 

마지막으로 동전 5에도 같은 연산을 적용하면 아래가 정답이 될 것이다.

 

결론적으로 아래의 연산을 적용하면 계산할 수 있다.

dp[j] = dp[j - i]
i = 사용할 동전 가격
j = 계산할 가격의 경우의 수

 

<소스 코드>

위의 접근법을 이용하여 코드로 구현한 결과이다.

import sys

n, k = map(int, sys.stdin.readline().split())
coin = []
for _ in range(n):
    coin.append(int(sys.stdin.readline()))

dp = [0 for _ in range(k + 1)]
dp[0] = 1

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

print(dp[k])