동전 교환

문제

• 여러 단위의 동전들이 주어져 있을 때, 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 될까?
• 각 단위의 동전은 무한정 쓸 수 있다.
• n: 동전의 종류 갯수
• m: 거슬러 줄 금액
• 출력: 거슬러 줄 동전의 최소 갯수를 출력

soltuion

n = int(input())  # 동전 종류 갯수
coins = list(map(int, input().split()))
coins.sort(reverse=True)  # 큰 숫자부터 탐색을 해야 가장 최소 탐색 가능
m = int(input())  # 거슬러줘야할 금액
ret = 2147000000


def recursive(level, sum):
    global ret
    if level > ret:  # 예를들어, 레벨3 수준에서 (5,5,5)로 ret=15 탐색이 완료되었을 때, 다음 레벨로의 탐색을 수행하지 않기 위해서 조건을 걸어줌. cut-edge
        return
    if sum > m:
        return
    if sum == m:
        # 작은걸로만 계속 깊이 탐색해서 답을 찾는 경우를 제외하기 위해
        if level < ret:  # level: 동전의 사용 갯수
            ret = sum
    else:
        for i in range(n):
            recursive(level + 1, sum + coins[i])


recursive(0, 0)
print(ret)

• 이 문제는 동적으로 푸는것이 더 현명하지만 재귀를 연습하기 위해 재귀 사용
• 문제에서 시간 복잡도를 줄이기 위해 cut-edge 할 수 있는 조건을 판별하는것이 관건
  • 그렇지 못하면 시간이 굉장히 오래 걸릴 수 있다.