백준 2293번: 동전 1 (Python)

접근

dp[m] 에 m 원을 만드는 동전의 조합수를 저장하여 문제를 풀 수 있다.

입출력 예시를 보면, 첫 동전으로 1원이 주어진다. 1원만 가지고 1원부터 10원까지 만들 수 있는 경우의 수는 1개이다.

여기에 2원을 추가하여, 1개 이상의 2원을 이용하여 동전을 구성한다고 생각해보자. 이 때는 1원, 2원을 자유롭게 사용하여 m - 2원을 만든 후 2원을 추가해주면 2원을 1개 이상 사용한 동전 경우의 수를 구할 수 있다.

이러한 방법을 통하여 t 원짜리 동전이 추가될 때 dp[j] += dp[j - i] 점화식을 이용하여 코드를 구성해주면 된다.

	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]
i = 1	(1)	1 경우 1	1 + 1 경우 1	1 + 1 + 1 경우 1	1 + 1 + 1 + 1 경우 1	1 + 1 + 1 + 1 + 1 경우 1	1 + 1 + 1 + 1+ 1+ 1 경우1
i = 2			2 경우 1	1 + 2 경우 1	1 + 1 + 2 2 + 2 경우 2	1 + 1 + 1 + 2 1 + 2 + 2 경우 2	1 + 1 + 1 + 1 + 2 1 + 1 + 2 + 2 2 + 2 + 2 경우 3
i = 3						5 경우 1	1 + 5 경우 1

(예시 입출력의 dp[6]까지 동전 구성 예시)

코드

import sys

n, m = map(int, sys.stdin.readline().split())
coin = [int(sys.stdin.readline()) for _ in range(n)]
dp = [0 for _ in range(m + 1)]
dp[0] = 1
for i in coin:
    for j in range(i, m + 1):
        if j - i >= 0:
            dp[j] += dp[j - i]
print(dp[m])

더 생각해 볼 것?

dp 문제는 점화식이 무엇인지를 생각해내지 못하면 접근도 못하는 문제가 대부분인것 같다. 다양한 dp 문제를 접하여 점화식 구성을 연습해야겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!