[백준 2839번] 설탕 배달 – 가장 적은 봉지 수로 배달하기

문제 개요

문제 링크 : https://www.acmicpc.net/problem/2839

 

위 문제를 쉽게 얘기하면

 

우리는 설탕 배달을 맡은 배달원입니다.

설탕을 포장할 수 있는 봉지는 딱 두 종류 뿐입니다.

• 5kg 봉지
• 3kg 봉지

이제 고객이 N kg의 설탕을 주문했습니다.

당신은 이 설탕을 최대한 적은 수의 봉지로 포장해야 합니다.

 

만약 정확히 N kg을 만들 수 없다면?

-1을 출력하세요.

 

예를 들어 입력이

18

 

이렇게 들어왔으면

• 총 설탕 18kg을 배달해야 함
• 가능한 포장 방법
  • 5kg x 3개 = 15kg
    • 나머지 3kg → 3kg x 1개
    • 총 4봉지가 나오게 됩니다.

이걸 직접 풀어보면 다음과 같습니다.

배달원	설탕 (kg)	포장 봉지 (kg)	남은 설탕 (kg)
1	18	5	18 - 5 = 13
2	13	5	13 - 5 = 8
3	8	5	8 - 5 = 3
4	3	3	3 - 3 = 0

 

 

여기서의 중요한 포인트는 5kg 봉지를 최대한 먼저 쓰고,

남는 걸 3kg 봉지로 채우는 것이 좋습니다.

 

5kg은 더 크므로 많이 쓰는게 봉지 수를 줄이는 데 유리합니다.

그래서 매번 5kg 봉지를 하나씩 줄여가며 3kg으로 나누어 떨어지는 순간을 찾으면 됩니다.

 

코드

import sys

def solve():
    N = int(sys.stdin.readline().strip())  # 총 설탕 무게

    # 5kg 봉지를 최대한 많이 써보면서 시도
    for five in range(N // 5, -1, -1):  # five = 5kg 봉지 개수
        rest = N - five * 5  # 남은 무게

        # 남은 무게가 3kg 봉지로 나눠지면 정답
        if rest % 3 == 0:
            three = rest // 3  # 3kg 봉지 개수
            print(five + three)  # 총 봉지 수 출력
            return

    # 어떤 조합으로도 안 나눠지면 -1
    print(-1)

if __name__ == "__main__":
    solve()

 

 

시간복잡도는 다음과 같습니다.

단계	시간
5kg 시도 반복	`O(N // 5)`
각 시도에서 나머지 계산	`O(1)`
전체	`O(N)` → 충분히 빠름 (N ≤ 5000 정도까지도 OK)