그리디 알고리즘

❗️ 계속해서 업데이트 될 예정...

잘못된 부분이 있다면 알려주세요 🙏

그리디 알고리즘

그리디 알고리즘(Greedy Algorithm)

매 단계에서 가장 최적의 선택을 하는 알고리즘.

탐욕 선택 속성

앞의 선택이 이후의 선택에 영향을 주지 않는 것.

최적 부분 구조

부분 문제를 최선의 해결책으로 풀면 전체 문제 또한 해결되는 구조.

그리디 알고리즘 풀이

---

문제 11047

✏️ 내가 작성한 코드

N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]
cnt = 0
for coin in coins[::-1]:
    if K//coin > 0:
        cnt += K//coin
        K %= coin
        if K == 0:
            break
print(cnt)

동전의 종류를 내림차순으로 바꾼 뒤, 가장 큰 값부터 나누기를 하는 방식으로 구할 수 있다. 즉, 가장 비싼 동전부터 나누는 방식이다.