BOJ 2624 동전 바꿔주기

태그

다이나믹 프로그래밍

URL

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

문제 설명

•

주어진 여러 동전을 제한된 개수 내에서 사용하여 특정 금액 T를 만드는 방법의 수를 구하는 문제

예제 입력/출력

•

입력1

Plain Text
복사

•

출력1

Plain Text
복사

제약 조건

•

0<T≤10,0000 < T ≤ 10,0000<T≤10,000

•

0<k≤1000 < k ≤ 1000<k≤100

◦

0<pi≤T0 < p_i ≤ T0<pi​≤T

◦

0<ni≤1,0000 < n_i ≤ 1,0000<ni​≤1,000

문제 풀이

접근1 브루트 포스 (완전 탐색) - O(2k⋅n)O(2^{k \cdot n})O(2k⋅n)

접근2 그리디

•

접근3 DP - O(T⋅k⋅n)O(T \cdot k \cdot n)O(T⋅k⋅n)

◦

이 문제는 동전의 개수가 제한된 배낭 문제로 볼 수 있다.

◦

DP 테이블 정의

▪

dp[m]: 금액이 m일 때, 만들 수 있는 경우의 수

•

1≤m≤T1 ≤ m ≤ T1≤m≤T 

◦

DP 관계식

for coin, n in coins:
	for money in range(T, 0, -1):
	    for cnt in range(1, n + 1):
	        if money - coin * cnt >= 0:
		          dp[money] += dp[money - coin * cnt]
Python
복사

▪

각 동전 (pip_ipi​, nin_ini​)에 대해

•

동전의 개수만큼 반복하며 DP 배열을 갱신

•

money원부터 1원까지 뒤에서부터 감소하면서 값을 갱신

◦

초기값 처리

▪

dp[0]=1dp[0] = 1dp[0]=1

•

0원을 만드는 방법은 아무 동전도 사용하지 않는 1가지 방법

풀이 코드

import sys
input = sys.stdin.readline

T = int(input())
k = int(input())

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

dp = [0] * (T + 1)
dp[0] = 1

for coin, n in coins:
    for money in range(T, 0, -1):
        for cnt in range(1, n + 1):
            if money - coin * cnt >= 0:
                dp[money] += dp[money - coin * cnt]

print(dp[T])
Python
복사

참고 자료

TISTORY2624. 동전 바꿔주기 (Python)