[백준 2839번] 설탕 배달 (파이썬)

문제

2839번: 설탕 배달

답

시행착오

처음에 그리디로 풀었다.

(5로 최대한 나누고, 나머지를 3으로 나누기)

 

그러나 그리디로 풀면 안풀리고, 브루트 포스로 풀면 풀리는 케이스가 존재한다.

e.g.) 11

그리디 ㅡ> 5*2 +1
브루트 포스 ㅡ> 5*1 + 3*2

 

답

N = int(input())
bag = 0
a = 0 # 나누어 떨어지면 a=1로 바꾼다


for i in range(N//5, -1, -1):
  bag = i
  M = N - 5*i # M : 남은 무게
  

  bag += M//3
  if M%3 == 0:
    print(bag)
    a = 1
    break

if a==0:
  print(-1)

개선된 답

N = int(input())
bag = -1


for i in range(N//5, -1, -1):
  M = N - 5*i # M : 남은 무게
  
  if M%3 == 0:
    bag = i + M//3
    print(bag)
    break

if bag == -1:
  print(-1)