[Python] 백준 11047번 - 동전 0

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

11047번: 동전 0

 

회의실 배정 문제를 제외하면 그리디는 처음 풀어본 것 같다.

정해진 틀이 있는 게 아니라 알고리즘 생각하고 구현하는 느낌이라서 풀면서 내가 지금 그리디로 잘 풀고 있는 게 맞나? 의문이 들었다.

 

가장 큰 동전부터 사용하기 위해서 입력받은 동전의 가치들을 역순으로 정렬한 후 for문을 사용하여 가능한 동전 수를 구하였다.

어쨌든 가장 큰 것부터 했으니까.. 그리디가 맞는 것 같다..

 

n, k = map(int, input().split()) #n:동전 종류, k:가치의 합(k원)
A = [0 for i in range(n)] #동전의 가치를 저장하는 리스트
for i in range(n):
    A[i] = int(input())

count = 0 #동전 개수
A.sort(reverse=True)
for i in range(n):
    if A[i] <= k:
        share = k//A[i]
        k -= share*A[i]
        count += share
print(count)