[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)
지폐를 동전으로 교환하는 방법의 가지 수를 계산하는프로그램을 작성하시오.

방법의 수는 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

 

 

나의 코드

def DFS(L,sum):
    global cnt
    if sum>T:
        return
    if sum==T:
        cnt+=1
    else:
        print(L,sum)
        for i in range(count[L]):
            if L !=count[L]:
                DFS(L+1,sum+money[i])
            DFS(L+1,sum)

T=int(input())
k=int(input())
money=[]
count=[]
for _ in range(k):
    a,b=map(int,input().split())
    money.append(a)
    count.append(b)
cnt=0

DFS(0,0)

print(cnt)

흠.. 못풀었따.. 동전의 개수 만큼 더하냐 안더하냐 확인하려 하였지만 동전의 갯수만큼 반복하는 로직이 떠오르지않는다...!

 

강의 해설의 접근법을 다시 본뒤 위 오른쪽과 같은 로직으로 다시 접근하였다.

처음 접근한 방법으로는 종료 조건이 보이지 않았지만 수정된 로직접근으로는 L(레벨로) 종료 조건이 있었다.

 

 

수정한 코드

def DFS(L,sum):
    global cnt
    if sum>T:
        return
    if L==k: 
        if sum==T:
            cnt+=1
    else:
        print(L,sum)
        for i in range(count[L]+1):
            DFS(L+1,sum+money[L]*i)

T=int(input())
k=int(input())
money=[]
count=[]
for _ in range(k):
    a,b=map(int,input().split())
    money.append(a)
    count.append(b)
cnt=0

DFS(0,0)

print(cnt)

 

 

정답코드

import sys
sys.stdin=open("input.txt", "r")
def DFS(L, sum):
    global cnt
    if sum>m:
        return
    if L==n:
        if sum==m:
            cnt+=1
    else:
        for i in range(cn[L]+1):
            DFS(L+1, sum+(cv[L]*i))

m=int(input())
n=int(input())
cv=list()
cn=list()
for i in range(n):
    a, b=map(int, input().split())
    cv.append(a)
    cn.append(b)
cnt=0
DFS(0, 0)
print(cnt)

수정된 나의 코드와 일치한다.