[알고리즘] 백준 11047번 동전0

문제

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

11047번: 동전 0

 

문제 접근

그리디 알고리즘을 적용해 문제를 풀었다. 결국 큰 액수의 돈부터 사용해야 동전의 개수가 최솟값이 되므로 큰 값부터 접근해보자.

예를 들어 보자.

100원 500원 1000원 짜리 동전이 있고 1200원을 만들기 위해서는 1000원 1개, 500원 0개, 100원 2개로 총 3개의 동전이 최솟값이 된다. 

그대로 코드에 적용해보자.

 

코드

n,k = map(int,input().split())

coins = list()

for i in range(n):
    a = int(input())
    coins.append(a)

# 그리디하게 접근하기 위해 내림차순으로 리스트 정렬
coins.sort(reverse=True)

count = 0

for coin in coins:
    if k >= coin:
        count += k//coin
        k = k%coin

print(count)

 

 

배운점

1. 파이썬에서 내림차순으로 정렬하기 위해 sort(reverse=True) 처럼 사용 가능하다. 이런 사소한 것 까먹기 좋은 것 같다.