재귀함수를 이용한 문제 풀어보기 - 동전 교환

❓ 문제

다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

 

➡️ 입력 : 동전의 종류 개수 n (1 <= n <= 12), n개의 동전의 종류, 거슬러 줄 금액 m (1 <= m <= 500)이 각각 한 줄씩 주어짐.

➡️ 출력 : 거슬려 줄 동전의 최소개수

 

<ex>

3 종류의 동전이 있고 그 종류가 각각 1원짜리, 2원짜리, 5원짜리이다. 이 동전들로 총 15원을 만들어 거슬러 주려면 5원, 5원, 5원 이렇게 3개의 동전을 사용하면 가장 적은 수의 동전으로 교환이 가능하다.

 

 

 

💡 해결하기

➡️ 같은 종류의 동전을 여러 번 쓰는 것이 가능하므로 기본적으로는 중복순열 구하기의 원리를 이용하여 코드를 작성한다.

재귀함수를 이용해 중복순열 구하기 (tistory.com)

재귀함수를 이용해 중복순열 구하기

but 단순히 중복순열을 구할 때에는 뽑을 숫자의 개수가 정해져 있었지만 이번 문제에서는 뽑을 동전의 개수가 정해져 있지 않다.

따라서 이번 문제에서는 종료 조건을 뽑은 동전의 값을 누적한 값이 거스름돈의 값과 같을 경우로 정해야 한다. DFS 함수의 인자로 뽑힌 동전의 값을 누적하는 _sum을 넣어준다.

_sum에는 DFS 함수 재귀 호출 시 coins(n개의 동전 종류 리스트)에서 현재 index(for 반복문으로부터)에 해당하는 값을 누적해 주면 된다.

 

➡️ 최종적으로 구해야 하는 값은 최소 동전 개수이기 때문에 동전 개수를 기록할 변수(answer)를 하나 만든다. 위에서 뽑은 동전의 값이 거스름돈 값과 같을 경우 현재 실행 중인 함수가 종료된다고 하였는데, 이때 answer보다 현재 뽑혀진 동전의 개수가 더 작을 경우에 answer 값을 업데이트 하는 식으로 코드를 작성해야 한다.

따라서 함수의 인자로 동전의 개수를 나타내는 cnt를 넣어준다.

DFS 함수 재귀 호출 시 _sum에 동전 값이 누적됨과 동시에 cnt도 1씩 증가해야 한다.

 

➡️ 만약 _sum이 거스름돈인 m을 넘어가는 경우 답이 될 수 없으므로 현재 실행중인 함수를 종료한다.

 

➡️ 위 과정까지만 코드를 작성하면 시간 초과가 발생할 가능성이 아주 높다.

따라서 코드를 최적화 해주어야 하는데, 이것은 cnt와 answer가 같아지는 시점에서 현재 실행중인 DFS 함수를 종료함으로써 가능하다.

우리가 찾고자 하는 것은 최소 동전 개수이기 때문에 지금까지의 최소 동전 개수인 answer과 현재 뽑은 동전 개수인 cnt가 같아지게 되면 cnt가 answer보다 작을 가능성이 0이라는 뜻이므로 더 이상 살펴볼 필요 없이 바로 종료하면 된다.

 

➡️ 또한, 애초에 n개의 동전 종류 리스트인 coins를 내림차순 정렬한 후 DFS 함수를 실행시켜야 한다.

즉, 큰 값을 가진 동전을 먼저 이용해야 한다는 것이다.

만약 매우 작은 값이 coins 리스트의 앞쪽에 위치하게 된다면 큰 값이 앞쪽에 위치할 때보다 거스름돈에 이를 때까지 비용이 더 많이 들어 시간이 초과될 수 있다. 거스름돈에 이를 때까지 더 많은 과정을 거쳐야 하면 자연스럽게 cnt의 값도 더 커지므로 다음 경우의 수를 살펴볼 때에도 비효율적이다.

트리로 따지면 더 깊은 레벨의 노드까지 탐색해야 하는 것이다. 

 

 

 

💻 Python으로 코드 작성하기

 

# _sum : 뽑은 동전의 값 누적하기 위한 변수, cnt : 지금까지 선택한 동전의 개수
def DFS(_sum, cnt):      
    # DFS 함수 밖에 있는 answer 변수를 전역변수로써 사용하기 위해 global 사용
    global answer
    # answer과 cnt가 같아지면 더 이상 탐색할 필요 X
    if cnt == answer:    
        return
    # 뽑은 동전의 값들의 합이 거슬러 줄 금액보다 커질 경우
    elif _sum > m:
        return
    # 뽑은 동전의 값들의 합이 거슬러 줄 금액과 같이질 경우
    elif _sum == m:
        # cnt가 지금까지 가능한 최소 동전 개수인 answer보다 더 작다면  
        if answer > cnt:
            # answer의 값을 cnt로 업데이트
            answer = cnt
    else:
        # 그 이외의 경우 coins 리스트를 0번 index부터 돌며 동전 값과 뽑은 개수 누적해 나가기
        for i in range(0, n):
            DFS(_sum + coins[i], cnt + 1)

n = int(input())     # 동전의 종류 개수 
coins = sorted(list(map(int, input().split())), reverse=True)     # n개의 동전의 종류 (내림차순 정렬)
m = int(input())     # 거슬러 줄 금액
answer = 2147000000     # 거슬러 줄 동전의 최소 개수
DFS(0, 0)
print(answer)

 

 

 

📌 참고 강의

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) 대시보드 - 인프런 | 강의 (inflearn.com)

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의