문제
명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.
- 20 = 10×2
- 20 = 10×1 + 5×2
- 20 = 10×1 + 5×1 + 1×5
- 20 = 5×3 + 1×5
입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법의 수는 231-1을 초과 하지 않는 것으로 가정한다.
입력
첫째 줄에는 지폐의 금액 T(0<T ≤ 10,000), 둘째 줄에는 동전의 가지 수 k(0<k ≤ 100), 셋째 줄부터 마지막 줄까지는 각 줄에 동전의 금액 pi(0<pi ≤ T)와 개수 ni(0<ni ≤ 1,000)가 주어진다. pi와 ni사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에 동전 교환 방법의 가지 수를 출력한다. 방법이 없을 때는 0을 출력한다.
코드
t = int(input()) # 지폐 금액
k = int(input()) # 동전 가지 수
coins = [[0, 0]]
for _ in range(k):
coins.append(list(map(int, input().split())))
dp = [[0] * (t+1) for _ in range(k+1)] # 행은 코인 인덱스, 열은 금액
dp[0][0] = 1
for i in range(1, k+1): # 동전 인덱스
p, n = coins[i]
for money in range(t+1): # 금액
dp[i][money] = dp[i-1][money]
for j in range(1, n+1): # 코인 개수
if money-p*j >= 0:
dp[i][money] += dp[i-1][money-p*j]
else:
break
print(dp[k][t])
dp 배열의 행은 코인이 저장된 배열 coins의 인덱스, 열은 금액이다. dp 배열의 값에는 해당 금액을 갖고 있는 동전으로 만들 수 있는 방법의 수가 저장된다.
이제 dp배열의 값을 채워줄 것인데, 우리는 최종적으로 dp[k][t]에 모든 경우의 수를 고려했을 때를 저장되게 할 것이므로 우선 coins 배열의 이전 인덱스까지의 코인들로 그 금액을 만들 수 있는 경우의 수를 dp배열에 저장해준다.
dp[i][money] = dp[i-1][money]
그리고 코인의 개수만큼 for문을 돌며 다음 식을 수행한다.
dp[i][money] += dp[i-1][money-p*j]
현재 보고 있는 금액이 p인 코인을 j개 더하면 금액 money를 만들 수 있는 경우의 수를 구하는 것이다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 1106번 호텔 (0) | 2023.05.28 |
---|---|
[Python/파이썬] 백준 22871번 징검다리 건너기 (large) (0) | 2023.04.30 |
[Python/파이썬] 백준 5557번 1학년 (0) | 2023.04.15 |
[Python/파이썬] 백준 2225번 합분해 (1) | 2023.04.15 |
[Python/파이썬] 백준 9251번 LCS (0) | 2023.04.14 |