거스름돈 문제는 전형적인 Greedy 알고리즘의 한 예로 알고있다.
이 문제에서는 거슬러 줄 수 있는 동전 단위가 2개여서 2개의 단위로 거슬러 줄 수 없는 돈을 예외 처리 해준다면 복잡하지 않았다.
Greedy
change = int(input()) #거슬러줄 돈
cnt = 0 #거슬러준 동전 개수
while change > 0: #동전 단위 (5원, 2원)
if change % 5 == 0:
cnt += change // 5
break
change -= 2
cnt += 1
print( -1 if change < 0 else cnt) #거슬러 줄 수 없다면 -1 아니면 cnt코드 설명
- 가장 큰 액수 동전으로 최대한 많이 거슬러 주는것이 핵심이다.
- 5원으로 다 거슬러주지 못할 경우에는 2원을 1개씩 거슬러주면서 최대한 5원으로 거슬러 주게끔 만들어준다.
- 시간복잡도 O(n)
거스름돈 문제는 Greedy말고도 backtracking으로도 풀 수 있는 문제이다.
왜냐하면 5원과 2원으로 거슬러 줄 수 있는 경우에만 탐색해도 최적해을 얻을 수 있기 때문이다.
거슬러줄 수 있는 조건에 부합한 경우를 탐색하면서 가장 적은 동전 수를 거슬러 주는 방법을 찾는것이다.
Backtracking
change = int(input())
max_c = change // 5 # 5원을 최대로 거슬러 줄 수 있는 개수
cnt = 0 # 가장 적게 거슬러 주는 동전 수
for i in range(0,max_c+1):
if (c := change - 5*i) % 2 == 0: #거슬러 줄 수 있는 조건
cnt = i + (c//2)
print(-1 if cnt == 0 else cnt)코드 설명
- 거슬러 줄 수 있는 조건에 부합한 경우만 탐색
- cnt가 업데이트 될때 비교하지 않고 바로 저장하는 이유
: 반복하면 할 수록 5원으로 최대한 많이 거슬러주기 때문이다.- 시간복잡도 O(n)
위와 시간복잡도가 같지만 조건에 부합하는 모든 경우를 찾아봐야하기 때문에 위보다는 시간이 더 걸린다.
하지만 5원을 0개부터 나눠준 경우 보다 최대한 많이 거슬러 준 경우가 해답에 가깝기 때문에 반복할때 탐색범위를 거꾸로 하는것이 더 좋을것이다.
위의 코드에서 최적화
change = int(input())
max_c = change // 5
cnt = float('inf') # 무한대로 초기화
for i in range(max_c,-1,-1): # 거꾸로 탐색
if (c := change - 5*i) % 2 == 0:
if cnt > i+(c//2): # 최소 거스름 동전 개수 비교
cnt = i+(c//2)
print(-1 if cnt == float('inf') else cnt)위의 코드와 다른점
- cnt값을 무한대로 초기화
: 최대한 적은 값이 업데이트되기 때문이다.- cnt 값을 비교하는 조건
: 거꾸로 탐색하기 때문에 반복할 수록 5원을 적게 거슬러주게됨
➡️ 값이 점점 커지게 업데이트됨
위 3개의 시간을 비교하자면 순서대로
40 ms , 48 ms , 44 ms
그리디 알고리즘이 가장 빨랐다.
