[백준] 10162번-(Python 파이썬) - Greedy

문제링크 : https://www.acmicpc.net/problem/10162

이번 문제는 그리디 알고리즘으로 해결하였다.
그리디(탐욕)알고리즘은 욕심쟁이 알고리즘이라고도 불리는데 여러 유형을 풀다보면 왜 욕심쟁이인지 알 수 있다. 뒤는 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 방식이다. 그런 이유로 DP(동적계획법)와 상반(?)되는 느낌이 강하다. 그리디는 100퍼센트 최적해를 보장해주지는 않지만 문제 유형에 따라 매우 빠른 경우가 많다. 두 가지다 문제 유형마다 장단점이 있으므로 문제를 읽고 어떤 알고리즘이 더 적합하고 빠를지 본인이 판단하고 풀어내면 될듯하다.

그리디 알고리즘의 대표적인 유형인 거스름돈 문제와 매우 비슷하다.
입력받은 시간이 10으로 나누어 떨어지지 않으면 -1을 출력하고,
나누어 떨어진다면 300, 60, 10으로 각각 나눠 준다. 나눌 때 몫을 순서대로 저장해두었다가 마지막에 순서대로 출력해주면 된다.

n = int(input())

a = [300, 60, 10]
b = []
if n % 10 != 0:
  print(-1)
else:
  for i in a:
    if n >= i:
      b.append(n // i)
      n = n % i
    else:
      b.append(0)
  for i in b:
    print(i, end=' ')