백준 2293번: 동전 1 [python]

kimminjunnn·2025년 7월 12일

알고리즘

목록 보기

121/318

난이도 : 골드 4
유형 : DP 심화
https://www.acmicpc.net/problem/2293

문제

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

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

입력

첫째 줄에 n, k (1<=n<=100, 1<=k<=10,000)

출력

첫째 줄에 경우의 수 출력, 경우의 수는 2^31 보다 작다.

문제 접근

어떠한 가치를 지닌 동전을 사용하여 목표 가치 k를 표현할 수 있는 경우의 수를 구하는 문제이다.

예제 1은 1, 2, 5 의 가치를 지닌 동전을 통해 목표 가치 10에 도달할 수 있는 경우의 수는

1,1,1,1,1,1,1,1,1,1
1,1,1,1,1,1,1,1,2
1,1,1,1,1,1,2,2
1,1,1,1,2,2,2
1,1,2,2,2,2
2,2,2,2,2
1,1,1,1,1,5
1,1,1,2,5
1,2,2,5
5,5

이렇게 10가지이다.

어떻게 풀 수 있을까

핵심 아이디어

이 문제는 동전의 조합을 통해 목표 금액을 만드는 경우의 수를 구하는 전형적인 DP(다이나믹 프로그래밍) 문제다.
특히, 동전의 순서는 고려하지 않으며, 각 동전은 무한히 사용할 수 있다는 점에서 중복 조합(Unbounded Knapsack) 유형으로 접근할 수 있다.

해답 및 풀이

dp[target] 을 target을 만드는 방법의 경우의 수로 놓는다.
동전 하나씩 순회하면서, 해당 동전을 사용해 만들 수 있는 가치부터 target까지를 업데이트한다.
점화식은 dp[value] += dp[value - coin]인데 어떻게 나온거냐면
dp[value - coin]는 value - coin원을 만들 수 있는 모든 경우
여기에 coin을 하나씩 추가하면 value원을 만드는 새로운 방법이 생김
따라서 dp[value] += dp[value - coin]

동전 리스트를 바깥쪽 루프를 둠으로써 순서가 다른 경우를 중복으로 세지 않게 처리할 수 있다.

import sys
input = sys.stdin.readline

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

dp = [0] * (target + 1) # 0부터 target까지 만드는 방법의 경우의 수
dp[0] = 1 # 0원을 만드는 방법은 '아무것도 선택하지 않는 방법' 1가지

for coin in coins: # 동전 리스트를 바깥쪽에 두어 중복을 세지않게 처리함
    for value in range(coin, target+1):
        dp[value] += dp[value-coin]

print(dp[target])

예제 코드 흐름

n = 3, target = 10  
coins = [1, 2, 5] 일때


for coin in coins:
	for value in range(1, target + 1):
    	dp[value] += dp[value - 1]
는

for coin in coins:
	for value in range(1, 11):
		dp[value] += dp[value-1] 이 되어

코인이 1일때,

value	계산	dp 결과
1	dp[1] += dp[0] → 1	[1, 1, 0, ...]
2	dp[2] += dp[1] → 1	[1, 1, 1, ...]
...	...	...
10	dp[10] += dp[9] → 1	[1, 1, 1, ..., 1]

dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
이 되고

코인이 2일때,

'for value in range(2, 11):
    dp[value] += dp[value - 2]

value	계산	dp 결과
2	dp[2] += dp[0] → 2	[1, 1, 2, ...]
3	dp[3] += dp[1] → 2	[1, 1, 2, 2, ...]
4	dp[4] += dp[2] → 3	[1, 1, 2, 2, 3, ...]
...	...	...
10	dp[10] += dp[8] → 6	[1, 1, 2, ..., 10]

dp = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
가 되며

마지막 코인이 5일때,

for value in range(5, 11):
    dp[value] += dp[value - 5]

value	계산	dp 결과
5	dp[5] += dp[0] → 4	[1, 1, 2, 2, 3, 4, ...]
6	dp[6] += dp[1] → 5	[1, 1, 2, 2, 3, 4, 5, ...]
7	dp[7] += dp[2] → 6	...
...	...	...
10	dp[10] += dp[5] → 10	[1, 1, 2, 2, 3, 4, ..., 10]