Algorithms-[Greedy] (백준 #11047 [동전0])

Greedy(탐욕법) 알고리즘은 생각하기 단순하면서 강력하다. Greedy의 제일 핵심은 "매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려 하지 않는 것" 이다. 대부분의 탐욕법 문제는 가장큰 순서대로, 가장 작은 순서대로등의 힌트가 문제에 주어진다. 이 문제는 위에서 말했듯이 나중에 미칠 영향을 고려하지 않기 때문에 Greedy로 문제를 짜려면 미리 이 문제에 이 알고리즘을 적용해서 최적의 해가 나올지를 생각해야 한다. 즉, 문제를 먼저 정확히 이해해야한다. 대표적인 문제로는 거스름돈 문제로 백준의 #11047j번 동전0이 있다.

11047번: 동전 0

My answer

import sys
input = sys.stdin.readline

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

coin=[int(input()) for i in range(n)]
#coin.sort(reverse=True)

for i in coin[::-1]:
    sum+=k//i
    k%=i
    
print(sum)

Another answer

N,K=map(int,input().split())
M=[int(input())for i in range(N)][::-1]
c=0
for i in M:c+=K//i;K%=i
print(c)

대표적인 그리디 문제로, 가장 큰 동전을 많이 사용할 수록 최종적으로 가장 적게 사용하게 된다.

또한 문제 조건 상 가지고있는 동전의 단위는 오름차순으로 입력하기 때문에 따로 정렬할 필요도 없이

거꾸로 순회하면서 가장 단위가 큰 동전부터 계산하면 되는 문제다.