그리디 알고리즘_파이썬(1)

그리디 알고리즘은 효과적이나 해법이 정당하지 않을 수도 있음. 검토가 필요함.
유형 파악이 어렵다면 그리디로 접근해보고, 안되면 다이나믹 프로그래밍, 그래프 알고리즘으로 고민해보기.

동전 나누기

내 답안

#거슬러주어야 할 돈
#n = int(input("돈을 입력해주세요: "))

n = 1260
temp = n

#동전의 최소 개수
count = 0

while temp >= 0:
  if temp >= 500:
    c = temp//500
    temp = temp - (500*c)
    count += c
  if temp >= 100:
    c = temp//100
    temp = temp - (100*c)
    count += c
  if temp >= 50:
    c = temp//50
    temp = temp - (50*c)
    count += c
  if temp >= 10 :
    c = temp//10
    temp = temp - (10*c)
    count += c
  if temp == 0:
    break
print(temp, count)

답안

n = 1260
count = 0

# O(n)
array = [500, 100, 50, 10]

for coin in array:
  count+= n//coin
  n %= coin

print(count)