[백준 11047번] 동전 0

문제 개요

문제 링크: https://www.acmicpc.net/problem/11047

 

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있습니다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 

이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하는 문제입니다.

 

더 쉽게 얘기하면

 

어떤 나라에는 동전이 N종류가 있고,

각 동전은 가치는 서로 다르고, 단위가 클수록 더 값이 비싸다고 합니다.

그리고 우리는 지금 K원을 만들려고 합니다.

 

가능한 한 적은 개수의 동전으로 K원을 만드는 것입니다.

 

예를 들어 입력이

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

 

 

입력을 해석해보면

• 동전은 10종류 있음
• 만들어야 하는 금액: 4200원
• 사용할 수 있는 동전: [1, 5, 10, ..., 50000] (오름차순)

입력 예제를 토대로 문제를 풀어보면

• 가장 큰 50000원 → 너무 큼
• 5000원 → 큼
• 1000원 → 4장 사용 → 남은 금액 200원
• 100원 → 2개 사용 → 남은 금액 0원

총 사용한 동전 수 : 4 + 2 = 6개

 

사용 알고리즘

여기서 사용할 알고리즘은 Greedy(탐욕법) 입니다.

이 문제에서 가장 중요한 것은 항상 큰 동전부터 쓰는 것이 정답입니다.

 

모든 동전이 앞의 동전으로 나눠 떨어지게 주어지기 때문입니다.

위의 예시처럼 4200원의 경우 1000원단위 100원단위로 나룰 수 있습니다.

따라서 큰 것부터 채우면 더 이상 좋은 방법은 없습니다.

 

코드

import sys

def solve():
    # N: 동전의 종류 수, K: 목표 금액
    N, K = map(int, sys.stdin.readline().split())

    # 동전 목록 입력 받기 (오름차순으로 들어옴)
    coins = [int(sys.stdin.readline()) for _ in range(N)]

    # 가장 큰 동전부터 보기 위해 역순 정렬
    coins.reverse()

    count = 0  # 사용한 동전 수

    for coin in coins:
        if K >= coin:
            # 해당 동전으로 최대 몇 개까지 쓸 수 있는지 계산
            use = K // coin
            count += use
            K -= coin * use

        # 더 이상 동전이 필요 없는 경우 조기 종료
        if K == 0:
            break

    print(count)

if __name__ == "__main__":
    solve()

 

 

 

이 문제처럼 "큰 단위가 작은 단위의 배수일 때" 항상 큰 단위부터 쓰는 것이 최적입니다.

하지만, 동전 단위가 배수가 아닌 경우에는 그리디가 실패할 수 있습니다.

(예: 1, 3, 4 → 목표: 6 → 그리디는 4+1+1 → 3개, 하지만 3+3 = 2개가 정답)

 

시간 복잡도를 보게 되면 

연산	시간복잡도
입력 처리	O(N)
그리디 루프	O(N)
전체	O(N) (최대 10,000도 충분히 빠름)