99클럽 코테 스터디 14일차 TIL: 거스름돈 그리디

오늘의 문제: 14916. 거스름돈

오늘은 거스름돈을 계산하는 문제이다. 사실 거스름돈이 서로가 배수/약수 관계라면 단순 계산이 가능하겠지만 2원짜리 동전과 5원짜리 동전이기 때문에 무조건 거스름돈이 크다고 개수가 많지는 않다.

다만 문제 알고리즘 분류를 봐서도 알 수 있듯이 DP를 활용하여 해결하는 것이 가능하다. 거스름돈이 2씩 커질 때마다 1, 5씩 커질 때마다 1을 추가하는 배열을 만들면 선형시간으로 해결할 수 있는 것이다.

하지만 내가 예전에 풀었던 방식을 보면 아주 단순하게 수식으로 해결했다. 기본적으로 가장 거스름돈의 개수가 적을 때가 답이기에 무조건 5원을 우선적으로 내는게 맞긴하기에 그걸 우선적으로 생각한 수식이다.

n=int(input())
k=n%5
if n in [1, 3]: print(-1)
elif k%2==0: print(n//5+k//2)
else: print((n//5-1)+(k+5)//2)

처음에 생각했던 것보다 점점 방법이 단순해지긴 하지만, 예전의 내가 그리 멍청하지 않았다는 생각이 든다. DP로 해결하는 것도 충분한 의미가 있긴 하지만 빨리 풀 수 있는 방법이 있다면 빨리 풀어버리자.