백준 2839 - 설탕 배달

처음 든 생각

- 브루트 포스해도 시간 복잡도가 괜찮을까? -> 최대 50000이니깐 O(N)으로 한쪽으로만 탐색을 다 하면 충분하겠네

 

나의 답

import sys
input = sys.stdin.readline

N = int(input())

three = N // 3
five = 0
isPossible = False
result = 10000000

while three >=0:
    if (N - (three * 3)) % 5 == 0:
        five = (N - (three * 3)) // 5
        result = min(result, three + five)
        isPossible = True
    three -= 1

if isPossible:
    print(result)
else:
    print(-1)

 

사용될 3의 개수의 최댓값이 더 크므로 3의 개수를 기준으로 하나씩 줄여가면서 5의 개수를 판단해보기로 하였다.

 

3의 개수 * 3 만큼 값을 빼준 값이 5로 나누어떨어지면 그 때만 5의 개수를 계산하면 된다.

 

그 다음 연산은 코드를 보면 이해가 어렵지 않을 거라 생각한다.