가지고 있는 동전 중에서큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
만약 800원을 거슬러줘야 하는데 화폐 단위가 500, 400, 100원이라면?
문제 풀이를 위한 최소한의 아이디어를 떠올리고 정당한지 검토해야 함.
# <문제> 거스름돈
#%%
n = 1260
count = 0
# 큰 단위부터 차례로
array = [500, 100, 50, 10]
for coin in array:
count += n // coin # 해당 화폐로 거슬러줄 수 있는 동전 개수
n %= coin
print(count) # 전체 동전의 개수
#%% md
* 동빈나님 유투브에 풀어주신 코드
* 좀 더 직관적인 코드를 위해서 chatgpt로 리팩토링을 시행했다.
#%%
amount = 1260
coins = [500, 100, 50, 10]
total = 0
count = 0
for coin in coins:
count, amount = divmod(amount, coin)
total += count
print(total)
#%% md
* 이런 식으로 divmod를 사용할 수는 있는데 어차피 total 코드를 불러와야 하는 거면 비슷해보이긴 한다.
* 그래도 8ms -> 4ms로 초가 줄었으니 조금은 더 나은 코드일지도?
* divmod라는 함수 예전에 배운 것 같은데 한 번 더 알아간다..
#%% md
<문제> 거스름돈: 시간복잡도 분석
화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는O(K)
이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과 무관하며, 동전의 총 종류에만 영향을 받음.