💡 그리디 알고리즘

그리디 알고리즘이란?

현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 말한다.
그리디 알고리즘은 최적해를 구하는데 사용되는 방법이지만, 그것이 최적이라는 보장은 없다!

그리디 알고리즘 조건

1. 탐욕 선택 속성(Greedy Choice Property)
   : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조(Optimal Substructure)
   : 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다

📢 11047번 -동전

백준 문제 링크

🔎 풀이

사용언어 : python

1. 가장 큰 동전부터 생각
   그리디 알고리즘을 적용하여 값이 가장 큰 동전부터 채우는 방식으로 구현이 가능하다.

2. N : 동전의 종류 (오름차순 정렬)
   K : 동전을 적절히 사용해 만들어야 할 가치의 합(살 물건의 가격이라 생각하자)
   count: 동전 개수
   count에 가지고 있는 동전 중 가치가 가장 큰 동전[-1]으로 나눈 몫을 더한다.
   k는 거스름돈이라 생각하면 된다.
   다시 k를 두번째로 가치가 큰 동전으로 나눈 몫을 count에 더해준다.

3. 2번과정 반복

🔎 코드

N,K = map(int,input().split())
arr = [int(input()) for i in range(N)]
count = 0
coin = -1
# 반복
while K > 0:
	# 몫 = 동전의 개수
    count +=  K//arr[coin]
    # 거스름돈
    K %= arr[coin]
    coin -=1
print(count)