백준 11047
방법1. 그리디 알고리즘
그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야한다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.
(--동빈나 이코테--)
import sys
n, k = map(int, sys.stdin.readline().split())
coin = []
for i in range(n):
a = int(input())
coin.append(a)
coin.sort(reverse=True)
cnt = 0
for c in coin:
cnt += k//c
k %= c
print(cnt)
coin을 내림차순으로 정렬해주고, coin리스트에서 c는 각각의 동전을 나타내는데 k//c가 0이면 cnt에 더해주어도 0일테니 나눠지는 데까지는 나눠지고 k에는 나머지가 남을텐데 그 나머지를 k에 대입해 그 이후에 또한 나눠지는 동전으로 계속 나눠갈 것이다.
