그리디 알고리즘

그리디 알고리즘

그리디 알고리즘은 일반적인 상황에서 최적의 해를 보장하지 않을 때가 많습니다.
따라서, 코딩테스트 문제를 보고 그리디 알고리즘을 사용했을 때 최적의 해가 나오는지 추론할 수 있는
능력이 필요합니다.
(그리디 알고리즘이 일반적인 상황에서 최적의 해를 갖지 못하는 이유는 유튜브에서도 쉽게 찾아볼 수 있습니다.
그리디 알고리즘을 검색해서 찾아보시길 권해드립니다. 참고로 저는 동빈나 님과 코드없는 프로그래밍님을 참고했습니다.)

거스름 돈 문제 해결 아이디어

최적의 해를 빠르게 구하기 위해 "가장 큰 화폐 단위"부터 돈을 거슬러 주면 된다.

예시코드

n, money  = map(int, input().split())    //n,money에 값을 입력하고 공백으로 구분
wallet = []    //빈 wallet 리스트 생성

for i in range(n):    //n번 만큼 돈다
    coin = int(input())    //coin에 입력한 값을 넣어준다.
    wallet.append(coin)    //coin에 입력된 값을 wallet에 추가

wallet.reverse()    //리스트의 입력된 값들을 반대 순서로 뒤집어준다.
count = 0    //동전의 갯수를 셀 count 초기화

for coin in wallet:    //wallet 리스트 값들을 coin에 순서대로 대입하며 돈다
    count += money // coin    // money 값을 뒤집어진 wallet 리스트 값으로 나눠주고, count 추가
    money %= coin // 그리디 조건을 충족하기 위해 선언 (가장 큰 배수를 제거하기 위해 선언)

print(count)    //저장된 count 출력 

 

입력 예시