백준거스름돈파이썬 (1) 썸네일형 리스트형 백준 - 14916 - 거스름돈 [파이썬] 개발일지 쓰는 건 재밌다. 이제 두번째라 그런가 아니면 짤을 올릴 수 있다는 생각때문인가 1. 문제 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제분류 : 그리디 알고리즘 그리디 알고리즘의 대표적인 유형. 2. 이해 및 풀이 처음에는 냅다 빼서 횟수를 구해볼까도 싶었는데 아참참, 그리디 알고리즘이 성립하려면, 약수배수의 관계를 가져야 한다. 5원을 빼줄만큼 뺐을 때 남은 수가 2의 배수여야 한다. 만약에 남은 수가 2의 배수(짝수)가 아니라면? => 5원입장: 빼줄만큼 빼준 횟수-1, 2원입장: (빼줄만큼 뺀 수+5)에서 2를 나눠주면 된다. (참고) 빼줄만.. 이전 1 다음
