백준 2293번: 동전 1 (G4) - Python 풀이

문제 설명

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

요약) n가지 종류의 동전으로 k원을 만드는 경우의 수를 출력합니다. 동전의 중복 사용이 가능합니다.

예제 입력

3 10
1
2
5

예제 출력

10

• 5,5 / 1,1,1,1,1,1,1,1,1,1 / 1,2,2,5 / 1,1,1,1,1,5 / 2,2,2,2,2 / 1,1,2,2,2,2 / 1,1,1,1,2,2,2 / 1,1,1,1,1,1,2,2 / 1,1,1,1,1,1,1,1,2 / 1,1,1,2,5 로 총 경우의 수가 10가지입니다.

풀이 과정

dp[i]는 i를 만들 수 있는 경우의 수 입니다.

1) 1을 사용해서 10을 만들 수 있는 경우의 수 -> 1만 사용 가능
2) 2를 포함해서 10을 만들 수 있는 경우의 수 -> 1과 2 사용 가능
3) 5를 포함해서 10을 만들 수 있는 경우의 수 -> 1과 2, 5 사용 가능

3개의 경우를 통해 표를 그려보면 dp[i] = dp[i] + dp[i -coin] 이라는 점화식을 도출할 수 있습니다.
https://didu-story.tistory.com/440 저는 바로 이해 안 돼서 이 블로그 보면서 이해했습니다.

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
coins.sort()

# 1차원 DP
dp = [0] * (k + 1)
# 0을 만드는 경우의 수는 1개
dp[0] = 1

# 돈 종류별로 순회
for coin in coins:
    for i in range(coin, k + 1):
    	# 점화식
        dp[i] += dp[i - coin]

print(dp[k])

점화식 떠올리는 게 너무 어렵습니다!

오늘 정말 한 것도 없는데 벌써 너무 졸립니다.
지금 자고 내일 일찍 일어나야겠습니다.

안녕히 주무십쇼!