Algorithm - 동전 바꿔주기(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[동전 바꿔주기(DFS)]

 

명보네 동네 가게의 현금 출납기에는 k가지의 동전이 각각 n(1), n(2), ... , n(k)개씩 들어있다.

가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔주려고 한다.

이 때, 동전 교환방법은 여러가지가 있을 수 있다.

 

예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있으면 20원 짜리 지폐를 다음과 같이 4가지 방법으로 교환할 수 있다.

 

20원 지폐의 교환예시

 

입력으로 지폐의 금액(T), 동전의 가지수(k), 각 동전 하나의 금액(p)와 개수(n)이 주어질 때, 지폐를 동전으로 교환하는 방법의 수를 출력하는 프로그램을 작성하시오.

(단, 방법의 수는 2의 31제곱을 초과하지 않는 것으로 가정함)

 

 

*입력 설명

첫 번째 줄에는 지폐의 금액 T(0 ≤ T ≤ 10,000)이 주어진다.

두 번째 줄에는 동전의 가지수 k(0 ≤ k ≤ 10)이 주어진다.

세 번째 줄부터 마지막 줄까지는 각 줄에 동전의 금액p(0 ≤ p ≤ T)와 개수n(0 ≤ n ≤ 10)이 주어진다.

 

*출력 설명

첫 번째 줄에 동전 교환방법의 가지수를 출력한다.

단, 교환할 수 없는 경우는 존재하지 않는다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_59.txt', 'rt')

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

if __name__ == "__main__":
    T = int(input())
    k = int(input())
    cv = list()
    cn = list()
    for i in range(k):
        a, b = map(int, input().split())
        cv.append(a)
        cn.append(b)
    cnt = 0
    DFS(0, 0)
    print(cnt)
    
# 출력 : 4

 

input_59.txt(입력)

20
3
5 3
10 2
1 5

 

 

중요내용

1. DFS() 함수의 인자 L은 상태트리의 레벨인 동시에 동전 금액과 개수에 접근하는 인덱스 번호로 사용된다.
2. DFS() 함수의 인자 sum은 사용된 동전의 총 금액을 의미한다.
3. 상태트리의 가지(i)는 특정 종류의 동전을 사용했는지의 여부를 알려준다.
4. 리스트 cv에는 동전의 금액이 저장되고, 리스트 cn에는 동전의 개수가 저장된다.
5. 상태트리의 가지수는 리스트 cn에 들어있는 동전의 개수만큼 존재해야 하므로 for문에서 range()의 인자가 cn[L]+1이 된다.
6. if절의 sum > T 조건은 해당 코드의 시간복잡도를 개선하기 위한 용도로 사용되었다.