이 문제는 '그리디 알고리즘'이라는 개념을 적용하여 푸는 문제였다.
'그리디 알고리즘' 이란 탐욕적이라는 뜻의 그리디에서 따온 말로
어떠한 문제를 해결할 때 다음 단계를 생각하지 않고 지금 당장
최선의 선택을 하는 기법입니다.
예를 들면 한 반에서 가장 많은 수업 듣게 하기, 동전 거슬러 주기 등의 문제가
있으며, 실제 프로그래밍에 사용시 동적 프로그래밍과 함께 생각할 경우의 수가
많지만 코딩 테스트에서 쓰이는 그리디 알고리즘 같은 경우에는
i는 i-1의 배수와 같이 최선의 선택이 항상 최선이 되도록 제한을 둔다고 하네요
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
이렇게요!
그럼 문제를 풀어 볼게요.
n, money = map(int, input().split()) #동전 종류와 가진 돈
wallet = [] #동전 담을 지갑 리스트
for i in range(n): #동전 종류 만큼 반복할건데
coin = int(input()) #가진 동전의 값 입력하고
wallet.append(coin) #지갑 리스트에 추가합니다.
wallet.reverse() #가격을 오름차순으로 적기 때문에 내림차순으로 바꿔줍니다
count=0 #동전 개수를 구하는 것이 조건
for coin in wallet: #지갑 리스트에서
count = count + money // coin #코인으로 나눈 몫이 동전의 개수
money = money%coin #잔돈은 나머지
print(count) #동전의 개수 출력문제에 대한 풀이는 주석에 상세하게 달아두었지만,
이 문제에서 그리디 알고리즘을 활용? 했다 말할 수 있는 부분은
wallet.reverse()
이곳 입니다.
작은 가치의 동전부터 입력을 받기 때문에 리스트에는
[1,5, 10, 50 ...]
이런식으로 저장이 될 것입니다.
하지만 가장 최선, 최고의 선택을 해야하는 그리디 알고리즘에서는
문제 요건에 따라 동전 개수가 가장 작은 것이 좋은 선택이기 때문에
가장 큰 단위의 동전부터 계산해줘야 합니다.
그렇기 때문에 reverse()를 활용하여 가장 큰 단위의 값부터
나열했습니다.
재미있는 문제 였습니다~
