[백준] 11047 (실버4)

간단한 Greedy 알고리즘 문제이다.

n, k = map(int, input().split())
coin = []
for i in range(n):
    coin.append(int(input()))  
coin.sort(reverse=True)
count = 0

for i in range(n):
    count += k // coin[i]  # k 보다 coin이 크면 어차피 0 임
    k = k % coin[i]  # k에서 coin을 뺄 수 있는만큼 여러번 빼고 남은 값

print(count)

count = 0

for i in range(n):
    count += k // coin[i]  # k 보다 coin이 크면 어차피 0 임
    k = k % coin[i]  # k에서 coin을 뺄 수 있는만큼 여러번 빼고 남은 값

위의 소스코드는 동전 관련 문제에서 자주 보이는 알고리즘이다.
남은 값을 동전으로 나눈 몫만큼 count를 올리고, 남은 값을 동전으로 나눠 남은 나머지가 남은 값이 된다.