[백준/BOJ/2839] 설탕 배달

2839 | 설탕 배달

문제 접근 & 설계

1. 상근이는 Nkg의 설탕을 배달해야한다.

2. 설탕의 봉지는 3kg, 5kg이 있다.

3. 최대한 적은 봉지로 Nkg의 설탕을 배달하는 것이 목적

4. 만약 Nkg을 만들 수 없다면 -1을 출력

• 최대한 5kg으로 담아야하므로 탐욕법을 생각했다.

1. N이 5의 배수일 때 => 5kg로 모두 담으면 됨

2. N을 5로 나눈 나머지가 3의 배수 일때 => 먼저 5kg로 담고, 나머지는 3kg로 담으면 됨

3. N을 5로 나눈 나머지가 3의 배수는 아니지만 [5의 배수 + 3의 배수]로 나타낼 수 있을 때 => 3kg로 담아보고 나머지가 5의 배수이면 나머지들을 모두 5kg에 담으면됨, 이 경우에서 모두 3kg로 담아야 하는 경우도 나눠짐

4. 이외는 -1 출력

사용한 스킬

시간 복잡도

• while : O(n)

O(n)

개선

• 처음에는 케이스를 4가지로 나누어 코딩했는데 모든 케이스를 합쳐도 될 것 같다.

초기 코드

import sys

N = int(sys.stdin.readline())

cnt = 0

if N % 5 == 0:
    print(N // 5)
elif (N % 5) % 3 == 0:
    print((N // 5) + ((N % 5) // 3))
else:
    tmp = N
    while (tmp > 0):
        cnt += 1
        tmp -= 3
        if tmp % 5 == 0:
            print(cnt + (tmp // 5))
            exit(0)
    print(-1)

개선 코드

import sys

N = int(sys.stdin.readline())

cnt = 0 # 3kg의 개수
tmp = N

while (tmp >= 0):
    if tmp % 5 == 0:
        print(cnt + (tmp // 5))
        exit(0)
    cnt += 1
    tmp -= 3
print(-1)

코드 길이 : 314B -> 183B

• 핵심은 5kg로 많이 담아야하는 것이므로 3을 빼가면서 5로 나누어지는지 계속 확인을 한 후 5로 나누어지는 경우를 바로 찾으면 된다.

• N이 5의 배수인 경우에는 while문에 들어가자마자 바로 찾아진다.

• 만약 N이 3kg으로만 담을 수 있다면 tmp(=N)에서 3을 계속적으로 빼다가 tmp가 0이 돼서 cnt(=3kg의 개수)만 계산되어진다.

난이도

난이도	정답률(%)
브론즈1	33.899%

알고리즘 분류

• 수학
• 그리디
• DP

소스코드 📃