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

# 백준 2039 설탕 배달

n = int(input())

a = n // 3
result = 10000

num = n
while a > -1:
    num = n
    num -= 3 * a
    res = num // 5
    if num % 5 == 0:
        result = min(result, a + res)
    a -= 1

if result == 10000:
    print(-1)
else:
    print(result)

 

[문제풀이]

3과 5를 가지고 만들 수 있는 숫자를 일일이 계산해서 풀었다고 보는게 맞겠다.

3으로 최대한 나눌 수 있는 값을 기준으로 하였다

예를 들면 18이라는 숫자를 3으로 최대한으로 뺀다면 6번(= a) 뺄 수 있다

반복문을 통해 3으로 최대한 뺄 수 있는 수를 하나씩 빼가며 a -= 1 하여

a = 5이면 3을 5번 빼기 / 5를 0번 빼기

a = 4이면 3을 4번 빼기 / 5를 1번 빼기

해서 결론적으로

3을 1번 빼기 / 5를 3번 빼기

총 4번 그리고 빼고 난 나머지 또한 0이 되도록 만들기!!

 

 

알고리즘 분류를 보니까 다이나믹 프로그래밍이랑 그리디 알고리즘이었다

풀긴 풀었는데 어떤 알고리즘을 이용해서 푼게 아니라 잘 모르겠다....

다시 공부해야 할듯