백준 2839번 설탕 배달 파이썬

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

2839번: 설탕 배달

 

 

내 답안

N = int(input())
cnt = 0
while True:
    if (N % 5) == 0:
        cnt += (N // 5)
        print(cnt)
        break
    N -= 3
    cnt += 1
    if N < 0:
        print(-1)
        break

---

 

이 문제를 동적 프로그래밍으로 푸는 방법도 있다.

하지만 DP 공부를 덜 했기 때문에 내가 생각하는 알고리즘대로 코드를 짰다.



N이 5의 배수가 되는 순간 나눠주게 된다면 효율적인 개수가 되기 때문에

N이 5의 배수가 될 때까지 3씩 빼주는 코드를 짜봤다.

 

하지만 예제 문제의 4와 같이

3씩 빼주다가 N이 음수가 되는 순간 3와 5의 조합으로 이 문제를 해결할 수 없으므로 -1을 출력해 준다.