[백준] 14916 거스름돈

🌭 문제 설명

• 춘향이는 편의점 카운터에서 일한다.

• 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

• 예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

---

🍗 제한 사항

---

🎁 입출력 예시

• 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

• 거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

---

😎 나의 풀이

N = int(input()) # N = 13

count = 0

while True:
  if N % 5 == 0:
    count += N//5
    break
  else:
    N -= 2
    count += 1
    
  if N < 0:
    break

if N < 0:
  print(-1)
else:
  print(count)

1. 그리디를 이용해서 풀었다. 5원 짜리를 최대한 많이 쓰는 방식으로 하면 된다.
2. N이 5로 나누어 떨어지면 나눈 몫 만큼 count에 추가하고 반복문 종료.
3. 나누어 떨어지지 않으면 2원을 썼다고 가정하고 N에서 2를 빼고 count에 1추가
4. N이 음수가 되면 나눌 수 없기 때문에 반복문 종료.
5. 정확하게 나눌 수 없었으면 -1 출력, 아니면 count 출력

---

🧵 다른 풀이

import sys
input = sys.stdin.readline

n = int(input())
if n == 1 or n == 3:
    print(-1)
    sys.exit()
t = n // 10
print(2*t + (0, 2, 1, 3, 2, 1, 3, 2, 4, 3)[n%10])

1. 튜플형식으로 뭔가 담아서 푼거같은데 잘 이해는 안간다.

---

• 그리디를 이용한 좋은 문제