[백준] 2839번 설탕 배달(with python)

윤무무 2023. 1. 27. 02:39

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그

www.acmicpc.net

1. 정답 코드

n = int(input())
cnt = 0

while n >= 0:
  if n % 5 == 0: #5로 나누어 떨어질경우 
    cnt += (n//5)
    print(cnt)
    break
  n -= 3 #5로 나누어 떨어지지 않으면 3을 반복해서 빼준다
  cnt += 1
else: #5와 3 둘 다 나누어 떨어지지 않을 경우 -1 출력
  print(-1)

한 시간 정도 고민을 하다가 도저히,, 안되겠어서,, 구글링

이 문제는 greedy 알고리즘을 이용하는 문제이다.

5의 횟수가 많으면 많을 수록 좋으나, 3의 배수가 더해져 있을 때를 고려해야한다.

아으 어려워ㅠ