3067번: Coins
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해
www.acmicpc.net
문제
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.
동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N 가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.
편의를 위해 방법의 수는 231 - 1 보다 작다고 가정해도 된다.
출력
각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.
코드
for _ in range(int(input())):
n = int(input())
coins = [0] + list(map(int, input().split()))
m = int(input())
dp = [[0] * (m+1) for _ in range(n+1)] # i번째 동전까지 사용해서 금액 j를 만드는 방법의 수
for i in range(1, n+1):
dp[i][0] = 1
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = dp[i-1][j]
if j >= coins[i]:
dp[i][j] += dp[i][j-coins[i]]
print(dp[n][m])
Dynamic Programming을 이용한 배낭문제였다. 원래의 배낭문제와 살짝 다른 점이라면 물건의 개수에 제한이 없다는 점?
dp에는 i번째 동전까지 사용하여 금액 j를 만드는 방법의 수를 저장한다.
금액 0을 만드는 방법의 수는 1가지 방법뿐이므로 모든 행의 0열은 1로 초기화해준다.
해당 문제의 점화식은 다음과 같다.
만들고자 하는 금액 j보다 이번에 쓰려는 동전 coins[i]의 값이 더 크다면 이 금액을 만드는데에는 coins[i]를 쓰지 못하므로 i-1번째 동전까지만 사용해서 금액 j를 만드는 방법의 수를 그대로 갖고온다.
그렇지 않고 금액 j가 coins[i] 이상이라면 coins[i]를 안 쓰는 방법(dp[i-1][j])과 coins[i]를 하나 쓰는 방법(dp[i][j-coins[i]])를 더한 값이 dp[i][j]에 저장될 값이다.
처음에는 아래처럼 dfs로 풀어보려고 했는데 시간 초과로 실패했다.
def dfs(idx, total):
global ans
if total == m:
ans += 1
return
if idx >= n:
return
for i in range(m+1):
if total+coins[idx]*i > m:
break
dfs(idx+1, total+coins[idx]*i)
for _ in range(int(input())):
n = int(input())
coins = list(map(int, input().split()))
m = int(input())
ans = 0
dfs(0, 0)
print(ans)
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 1965번 상자넣기 (0) | 2023.10.28 |
---|---|
[Python/파이썬] 백준 17845번 수강 과목 (0) | 2023.10.25 |
[Python/파이썬] 백준 2629번 양팔저울 (0) | 2023.10.10 |
[Python/파이썬] 백준 20542번 받아쓰기 (0) | 2023.09.26 |
[Python/파이썬] 백준 4811번 알약 (0) | 2023.09.13 |