동전 바꿔주기(DFS)
명보네 동네 가게의 현금 출납기에는 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)
지폐를 동전으로 교환하는 방법의 가지 수를 계산하는프로그램을 작성하시오. 방법의 수는 2^31을 초과하지않는 것으로 가정한다.
▣ 입력설명
첫째 줄에는지폐의 금액 T(0<T≤10,000), 둘째 줄에는 동전의 가지 수k(0<k≤10), 셋째 줄부터 마지막 줄까지는 각 줄에 동전의금액 pi(0<pi≤T)와 개수 ni(0<ni≤10)가 주어진다. pi와 ni 사이에는 빈 칸이 하나씩 있다.
▣ 출력설명
첫 번째 줄에 동전 교환 방법의 가지 수를 출력한다.(교환할 수 없는 경우는 존재하지 않는다.)
▣ 입력예제 1
20
3
5 3
10 2
1 5
▣ 출력예제 1
4
import sys
# sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10000)
T = int(input()) #원하는 금액.
k = int(input())
data = []
p = list() #금액
t = list() #개수
for _ in range(k):
a,b = map(int, input().split()) #금액, 개수
p.append(a)
t.append(b)
cnt = 0
def DFS(L, sum):
global cnt
if sum > T:
return
if L == k: #끝까지 돔. 종료조건
if sum == T:
cnt += 1
else: #아직 도착안했다면... 각 동전별로 몇개 사용할지 상태트리 !
for i in range(t[L]+ 1): #현재 동전의 개수만큼 가지 뻗기.
DFS(L+1, sum + p[L] * i) #현재 동전 금액 x 사용할 개수 i
DFS(0,0)
print(cnt)코멘트
이 문제는 상태트리를 시각화 할 수 있었어야 했다. DFS(L,sum) 으로 기존과 같은 방식으로 넘긴다.
근데 이제 각 동전별로 상태트리를 그리는 것이었다 !!
예를 들어 위 예시처럼 5원짜리 3개, 10원 짜리 2개, 1원 5개
- 5원을 0,1,2,3 총 4가지 상태트리를 뻗고
- 10원 0,1,2 총 3가지 상태트리를 뻗을 수 있고. 이런 식으로 진행하는 것이다 !!!
그리고 해당 동전의 금액 x 개수를 sum에 더해주는거지.
그리고 Cut Edge. sum이 원하는 금액 넘어가면 컷하면 돼.
각 동전별로 트리 가지 뻗어나간다는 거 이해했어야 했다.
