[알고리즘] 동전 바꿔주기(DFS)

(문제) 동전 바꿔주기(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 사이에는 빈 칸이 하나씩 있다.

출력설명

첫 번째 줄에 동전 교환 방법의 가지 수를 출력한다.
(교환할 수 없는 경우는 존재하지 않는다.)

테스트케이스

입력예제	출력예제
20 3 5 3 10 2 1 5	4
19 4 4 4 5 3 2 3 7 3	8
150 7 1 11 3 20 7 15 12 10 13 15 25 10 47 5	6293
486 7 1 10 3 9 7 9 12 7 13 9 25 7 47 5	8248

---

해결방법

---

코드

# L은 레벨이면서 인덱스
def DFS(L, sum):
    global count
    if sum > t:
        return
    if L == k:
        if sum == t:
            count = count + 1
    else:
        # L 즉, 동전의 종류에서 동전의 개수 만큼 돌기
        for i in range(a[L][1]+1):
            DFS(L+1, sum + a[L][0] * i)

# 받은 돈
t = int(input())

# 동전의 종류 개수
k = int(input())

# 각각의 요소로 넣는다
a = [list(map(int, input().split())) for _ in range(k)]

count = 0

DFS(0, 0)

print(count)