백준 | [파이썬 Python] 11047 동전 0

---

배경

https://www.acmicpc.net/problem/11047

 

 

 

 

코드

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
coins = list()
for _ in range(n):
    coins.append(int(input()))

coins.sort(reverse=True)
result = 0
for coin in coins:
    if k >= coin:
        result += k // coin
        k %= coin
        if k <= 0:
            break

print(result)

 

 

설명

대표적인 그리디 문제이다. 그리디 문제란

그리디 알고리즘(탐욕 알고리즘)은 문제를 해결할 때 각 단계에서 최적이라고 생각되는 선택을 하는 방식입니다. 즉, 현재 단계에서 가장 좋다고 생각되는 선택을 하고, 이를 반복하여 문제를 해결하는 방법입니다. 이 알고리즘은 항상 전체 문제에 대한 최적해를 보장하지는 않지만, 많은 경우에 대해 좋은 근사해를 제공합니다.

 

동전 문제의 경우 가장 적은 동전을 거스르기 위해서 가장 큰 단위의 동전으로 많이 거슬러줘야 한다.

이를 기반으로 코드를 보면 동전을 단위가 큰 기준으로 정렬을 하고 최대한 많이 나눠주고 나눠 준 값을 계속해서 추적한다

 

배운 점