백준 11047 동전 0

문제

---

솔루션

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

li=[]
for _ in range(n):
    li.append(int(input()))
    
li.sort(reverse=True)

cnt=0
for i in li:
    if k>=i:
        cnt += (k//i)
        k %= i
        if k<=0:
            break
            
print(cnt)

---

깨달은 점

문제를 읽고 동전의 큰 값부터 나누면서 나머지를 저장하는 형식으로 해결했다.

이러한 해결법은 그리디알고리즘으로

그리디 알고리즘이란 뒷 일은 생각하지 않고 지금 당장 좋은 것만 선택하는 알고리즘이다.

(각 단계에서 최적이라고 생각되는 것을 선택 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘)