문제 : https://www.acmicpc.net/problem/5585

목표 :

• 500, 100, 50, 10, 5, 1 로 주어진 숫자를 최소의 개수를 사용해 만들어 보아라

조건 :

• 숫자는 1 이상 1000미만의 정수

푸는법 :

• 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식인 Greedy문제이다.

O(6) 풀이

rest = 1000 - int(input())
cnt = 0
for i in [500, 100, 50, 10, 5, 1]:
    if rest >= i:
        cnt += rest// i
        rest = rest % i

print(cnt)

O(1) 풀이

• rest // 500
  • 500을 쓸 때 경우의 수
  • 500이하의 수 나누면 0이다.
• rest // 100%5
  • 100을 쓸 때 경우의 수
  • %5는 위에서 count된 것을 포함시키지 않는다.
• rest // 50%2
  • 50을 쓸 때 경우의 수
• rest // 10%5
  • 10을 쓸 때 경우의 수
• rest // 5%2
  • 5을 쓸 때 경우의 수
• rest %5
  • 1을 쓸 때 경우의 수

rest = 1000 - int(input())
print(rest//500 + rest//100%5 + rest//50%2 + rest//10%5 + rest//5%2 + rest%5)