[백준] 2624 동전 바꿔주기

문제 링크

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

사용 알고리즘

• DP

풀이

3067 Coins과 유사하지만 사용 가능한 동전의 개수가 무한이 아니라는 점에 차이가 있는 문제이다.

 

dp 배열을 만들어야 하는 금액만큼 생성해준 뒤,

사용 가능한 모든 동전에 대해서 현재 금액에 도달할 수 있는 경우 해당 동전을 1 ~ 보유 수량만큼 사용했을 경우 도달한 금액에 현재 금액에 도달할 수 있는 경우의 수를 더해준다.

예시

Input

5
3
2 3
1 2
3 1

 

초기 상태

초기값인 dp[1][0]을 1로 설정해준다.

index	0	1	2	3	4	5
dp[0]	0	0	0	0	0	0
dp[1]	1	0	0	0	0	0

 

첫번째 동전(Value: 2, Count: 3)

과거 상태를 저장하는 dp[0] 리스트에 dp[1]을 복사한 뒤 dp[0][j] 에 도달할 수 있는 경우가 있다면( = 해당 금액을 만들 수 있다면)

동전의 금액과 수량을 곱한 dp 리스트의 해당 인덱스에 현재 금액에 도달할 수 있는 경우의 수를 더해준다.

index	0	1	2	3	4	5
dp[0]	1	0	0	0	0	0
dp[1]	1	0	1	0	1	0

 

두번째 동전(Value: 1, Count: 2)

위와 동일하게 처리해준다.

index	0	1	2	3	4	5
dp[0]	1	0	1	0	1	0
dp[1]	1	1	2	1	2	1

 

세번째 동전(Value: 3, Count: 1)

위와 동일하게 처리해준다.

index	0	1	2	3	4	5
dp[0]	1	1	2	1	2	1
dp[1]	1	1	2	2	3	3

 

최종적으로 제공된 동전으로 5를 만들 수 있는 경우는 3가지인 것을 알 수 있다.

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

t, k = int(input()), int(input())
coins = [[int(x) for x in input().split()] for _ in range(k)]

dp = [[0] * (t + 1) for _ in range(2)]
dp[1][0] = 1
for i in range(k):
    coin = coins[i]
    for j in range(t + 1): dp[0][j] = dp[1][j]
    
    for j in range(t + 1):
        if not dp[0][j]: continue
        for l in range(1, coin[1] + 1):
            if coin[0] * l + j <= t:
                dp[1][coin[0] * l + j] += dp[0][j]
print(dp[-1][-1])