설탕 배달

import sys


def main():
    input = sys.stdin.readline
    inf = float("inf")

    n = int(input())

    min_count = inf

    for count_3 in range(n // 3 + 1):
        for count_5 in range(n // 5 + 1):
            if count_3 * 3 + count_5 * 5 == n:
                count = count_3 + count_5
                min_count = min(min_count, count)

    if min_count == inf:
        print(-1)
    else:
        print(min_count)


main()

import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    for count_5 in range(n // 5, -1, -1):
        rest = n - count_5 * 5
        if rest % 3 == 0:
            count_3 = rest // 3
            print(count_5 + count_3)
            break
    else:
        print(-1)


main()

정확하게 $N$ 킬로그램을 만들 수 있을 때, 필요한 $3$ 킬로그램 봉지와 $5$ 킬로그램 봉지의 개수는 각각 $N / 3$과 $N / 5$을 넘지 않습니다. 따라서 이 범위 내의 모든 봉지 개수 조합에 대해 합이 $N$이 되는 경우를 찾아가며 모든 경우에서 최소 봉지 개수를 찾으면 됩니다. $N \le 5000$이고 가장 많이 실행되는 경우 약 $N^2 / 15$번의 연산을 수행하므로 시간제한 내에 충분히 종료됩니다.

두 번째 코드는 $5$ 킬로그램 봉지의 개수를 먼저 정하고 남은 무게를 $3$ 킬로그램 봉지로 채울 수 있는지 검사하는 방식으로 구현하였습니다. 전체 개수를 줄이려면 $5$ 킬로그램 봉지를 최대한 많이 사용하는 것이 유리하므로 $N / 5$부터 $0$까지 줄여가며 확인합니다. 최대 연산 횟수를 약 $N / 5$으로 줄일 수 있습니다.