[Python] 백준 2839번 설탕 배달

그리디 문제이다. 이 문제의 핵심은 ‘5킬로그램짜리 봉지를 최대한 많이 사용하는 것’이다.

설탕을 3kg와 5kg짜리 봉지로 나누는 방법: 2가지 경우

1. 설탕 무게(N)가 5kg으로 나누어 떨어지는 경우

이때는 5kg짜리 봉지만 사용하면 되므로, N을 5로 나눈 몫을 구하면 된다.

예) 25를 나눌 때: 25 / 5 = 5

2. 설탕 무게(N)가 5kg으로 나누어 떨어지지 않는 경우

이때는 N이 5로 나누어 떨어질 때까지, N에서 3을 빼준다.

• 만약 반복적으로 3을 빼다가, 5의 배수가 나오면 5로 나눠준다.

  예)21킬로그램의 설탕을 나눌 때: 21-3-3=15, 15 / 5 = 3

• 만약 반복적으로 3을 빼다가, 음수가 나오면 3과 5로 만들 수 없는 수이므로 -1을 출력한다.

  예)22킬로그램의 설탕을 나눌 때: 22-3-3-3-3-3-3-3-3 = -2

• 만약 반복적으로 3을 빼다가, 0이 나오면 N은 3으로 나누어 떨어지는 수이다.

  예)21kg의 설탕을 나눌 때: 21-3-3-3-3-3-3-3=0

추가적인 연산 없이 반복문을 종료한다.

코드로 보면 더 이해하기 쉬운 문제이다.

N = int(input()) # 설탕 무게를 입력 받는다.
result = 0 # 봉지 총 개수 초기화


if N % 5 == 0: # N이 5kg으로 나누어 떨어지는 경우
    result = N // 5
    print(result)

else: # N이 5kg으로 나누어 떨어지지 않는 경우
    while N > 0: 
        N -= 3
        result += 1 # 3kg 봉지의 개수 +1
        if N % 5 == 0:
            result += N // 5 # 3kg 봉지의 개수 + 5kg 봉지의 개수
            print(result)
            break
        elif N < 0: # N을 3과 5로 나눌 수 없는 경우
            print(-1)