그리디(Greedy) 알고리즘 백준#11047 #실버 | "동전 0" | 파이썬 풀이

문제

문제 원본: https://www.acmicpc.net/problem/11047

11047번: 동전 0

접근법

본 문제를 한 줄로 요약하자면,

N가지 종류의 동전을 조합해 화폐 가치가 K원을 만들 때 필요한 동전의 최소 개수를 구하는 문제입니다.

본 문제는 그리디 알고리즘의 기초 예제인 거스름돈 문제와 변수 이름이나 표현방식이 다를 뿐 풀이 방법은 매우 흡사합니다.

그래서 저는 다음과 같이 일부 변수명을 거스름돈 문제에서 사용되는 변수명으로 바꾸었습니다.

"동전"을 "화폐"로, "동전 가치의 합"을 "거스름돈"으로 말이죠.

거스름돈 유형의 일반적인 접근법을 적극 적용한 풀이를 코드와 함께 살펴보겠습니다.

소스코드

# n: 화폐 종류 개수, k: 거스름돈
n, k = map(int, input().split())

# 화폐 종류 입력받기
money_list = [int(input()) for _ in range(n)]

# 정답: 거스름용 화폐 개수의 최솟값
answer = 0

# 화폐 종류 내림차순 정렬: 화폐 가치가 큰 순서대로 화폐 정보 추출
money_list.sort(reverse = True)
for money in money_list:
    # 필요한 화폐 개수 = 거스름돈을 특정 화폐로 나눈 몫
    answer+= k//money
    # 거스름돈 업데이트: 거스름돈을 특정 화폐로 나눈 나머지로 업데이트
    k%=money
    # 거스름돈이 0원인 경우
    if k == 0:
        break
# 정답 출력
print(answer)

일반적인 거스름돈 문제에서 최소 화폐 개수를 구할 때는 가장 큰 단위의 화폐부터 차례대로 필요한 화폐 개수를 결정합니다.

본 문제에서는 화폐 종류를 화폐 가치가 작은 것부터 오름차순으로 입력받습니다.

따라서 가치가 큰 화폐부터 거스름돈에 필요한 화폐 개수를 결정하기 위해,

11번째 줄에서 파이썬의 내장 정렬 함수인 sort를 사용하였습니다.

 

화폐 종류별 개수는 거스름돈을 특정 화폐로 나눈 몫으로 계산하였으며,

거스름돈은 해당 화폐로 나눈 나머지로 업데이트하였습니다.

예를 들어, 거스름돈(K)이 2,300원이고 주어진 화폐 단위가 100원, 500원(N=2)이라고 가정하겠습니다.

가장 먼저 가장 큰 화폐 단위인 500원짜리 화폐로 거스름돈을 최대한 많이 나눠줍니다.

이때 500원짜리는 총 4개를 사용하고 거스름돈으로 300원이 남습니다.

이제 500원짜리로 더 이상 나눌 수 없기 때문에 다음으로 큰 단위의 화폐인 100원짜리로 거스름돈을 나눠줍니다.

100원짜리 화폐는 총 3개 사용합니다.

최종적으로 이제 거스름돈이 0원이 되었기 때문에 거스름돈을 특정 화폐로 나누는 작업을 멈추고 정답을 제출합니다.

총 7개의 화폐 개수를 사용한 것이 정답이 되겠죠?

시간 복잡도: O(N)

화폐 종류 N번 만큼 연산을 반복하기 때문에 시간 복잡도는 O(N)입니다.

---

오늘은 그리디 알고리즘 중 거스름돈 문제에 해당하는 간단한 문제를 풀어봤습니다.

더 좋은 풀이가 있으시거나 포스팅 내용에 오류가 있을 경우 아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 건강하고 즐거운 하루 보내시길 바랍니다.

고맙습니다 :)