동전바뀌주기
명보네 동네 가게의 현금 출납기에는 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
을 초과하지않는 것으로 가정한다.
▣ 입력설명
첫째 줄에는지폐의 금액 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.txt", "r")
def DFS(L, sum): #여기서 L은 인덱스이면서 깊이를 의미한다.
global cnt
if sum>T: #레벨 3를 가기도 전에 이미 T=20이 넘는 경우
return
if L == k:
if sum==T:
cnt+=1
else:
for i in range(0, cn[L]+1): #range의 범위는 트리의 가지(자식) 수를 의미한다. 여기서 i는 동전의 갯수를 의미한다.
DFS(L+1, sum+ (cv[L]*i)) #동전의 종류 * 동전의 갯수 = 동전의 금액
if __name__=="__main__":
T=int(input())
k=int(input())
cv=[]
cn=[]
for i in range(k):
a, b = map(int, input().split())
cv.append(a)
cn.append(b)
cnt=0
DFS(0,0)
print(cnt)
Hint
▶ 동전의 금액(cv)와 동전의 갯수(cn)을 별도의 리스트로 만들어서 저장한다.
▶ L은 깊이를 의미함과 동시에 cv리스트와 cn리스트의 인덱스 역할을 한다.
▶ L==T의 깊이에 도달하기 전에 이미 sum이 T값을 초과하는 경우에는 return으로 경우의 수를 cutting해준다.
▶for i in range에서 range의 범위는 자식의 수를 의미한다.
▶sum에는 동전의 금액( =동전의 종류*동전의 갯수)을 더 해준다.
※ 재귀함수의 실제 동작 루트는 부모에서 L깊이까지 L도착시 L-1로 back하고
다시 L로 전진하고, L-1로 back하고
L-1에서 L을 다 훑는 경우
다시 L-2로 back한다.
그 다음 L-1에서 훑지 못했던 다음 자식을 훑는다.
'파이썬 알고리즘 > DFS, BFS 활용' 카테고리의 다른 글
6. 알파코드(DFS) (0) | 2022.11.10 |
---|---|
5.동전 분배하기(DFS) (0) | 2022.11.09 |
3. 양팔저울(DFS) (0) | 2022.11.09 |
2.휴가 (0) | 2022.11.09 |
1. 최대 점수 구하기 (1) | 2022.11.09 |