파이썬 코딩테스트 강좌, 동전 개수의 최솟값 구하기

안녕하세요! 오늘은 파이썬 코딩테스트에서 자주 출제되는 문제 중 하나인 동전 개수의 최솟값 구하기 문제를 다루어 보겠습니다. 이 문제는 특히 알고리즘과 그리디 문제를 이해하는 데 많은 도움이 되며, 여러 상황에서 활용될 수 있습니다.

문제 설명

당신은 다양한 동전을 가지고 있습니다. 각각의 동전은 유한한 개수로 존재합니다. 입력으로 주어진 금액을 잔돈으로 주기 위해 최소한의 동전을 사용해야 합니다. 주어진 동전의 종류와 목표 금액이 입력으로 주어지면, 최소한의 동전 개수를 출력하는 프로그램을 작성하시오.

입력 형식

  • 첫째 줄에 동전의 종류 n (1 ≤ n ≤ 100)과 목표 금액 k (1 ≤ k ≤ 10000)가 주어진다.
  • 둘째 줄에 n개의 동전의 가치가 공백으로 구분되어 주어진다. 각 동전의 가치는 서로 다르며, 1 이상 10,000 이하이다.

출력 형식

목표 금액을 만들기 위해 필요한 최소한의 동전 개수를 출력한다.

예제 입력

    3 11
    1 2 5

예제 출력

    3

문제 해결 방안

이 문제는 그리디 알고리즘을 이용하여 해결할 수 있습니다. 그리디 알고리즘이란 매 선택에서 최적이라고 판단되는 것을 선택하여 최종적으로 최적의 해를 구하는 방법입니다. 이 경우, 가장 큰 가치의 동전부터 최대한 많이 사용하는 방식을 취하면 됩니다.

단계별 접근법

  1. 가장 큰 동전 가치부터 시작하여, 해당 동전을 사용할 수 있는 최대 개수를 계산합니다.
  2. 잔액에서 사용한 동전의 가치를 빼고, 다음 큰 동전으로 넘어갑니다.
  3. 이 과정을 목표 금액을 0으로 만들 때까지 반복합니다.

코드 구현

이제 위의 접근법을 바탕으로 파이썬 코드를 구현해보겠습니다. 주어진 입력을 바탕으로 동전 개수를 카운트하는 코드를 작성합니다.

    def min_coins(n, k, coins):
        # 동전을 내림차순으로 정렬합니다.
        coins.sort(reverse=True)
        
        count = 0
        for coin in coins:
            # 현재 동전의 최대 개수를 계산합니다.
            if k == 0:
                break
            count += k // coin  # 해당 동전으로 몇 개 만들 수 있는지
            k %= coin  # 잔액 업데이트
        
        return count

    # 입력 받기
    n, k = map(int, input().split())
    coins = list(map(int, input().split()))

    # 결과 출력
    print(min_coins(n, k, coins))

실행 결과 분석

위 코드는 입력된 동전 가치와 목표 금액을 기반으로 동전을 최소 개수로 사용하는 과정을 보여줍니다. 예를 들어, 동전의 종류가 [1, 2, 5]이고 목표 금액이 11인 경우, 다음과 같은 과정을 통해 잔액을 줄여 나갑니다:

  • 5원 동전을 2개 사용: 잔액 1 (count = 2)
  • 1원 동전 1개 사용: 잔액 0 (count = 3)

시간 복잡도

이 알고리즘의 시간 복잡도는 O(n)입니다. n은 주어진 동전의 개수이며, 동전 리스트를 정렬하는 부분이 O(n log n)입니다. 따라서 전체 시간 복잡도는 O(n log n)로 간주할 수 있습니다.

주의 사항

동전 개수의 최솟값을 구하는 과정에서 주의해야 할 점은 동전이 반드시 존재한다는 보장이 없을 경우입니다. 예를 들어, 목표 금액을 만들 수 없는 경우 예외 처리를 통해 적절한 메시지를 출력하도록 할 수 있습니다.

마무리

이 문제를 통해 그리디 알고리즘에 대한 이해를 높일 수 있었기를 바랍니다. 다양한 동전 조합과 목표 금액을 시도하면서 알고리즘을 연습해 보세요. 코딩테스트에서 자주 출제되는 문제인 만큼 숙지하고 있으면 많은 도움이 될 것입니다.

© 2023 파이썬 코딩테스트 강좌