백준 - 2839. 설탕배달 (MJ)

📖2839. 설탕배달

백준 - 실버4

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

예제 1

input >> 18
output >> 4

예제 3

input >> 6
output >> 2

예제 5

input >> 11
output >> 3

예제 2

input >> 4
output >> -1

예제 4

input >> 9
output >> 3

🔍Institution

가장 먼저 생각난 것은 DP이긴 하지만, 그 전에 먼저 나열해본 후 규칙을 찾아봐야겠다는 생각이 들었다.

포인트 : 3, 5로 나누어 떨어지는가, 아니라면 어떻게 해야 할 것인가!

🔍Approach

3의 배수인 경우 → 3으로 나눈 값 or 5로 나눈 값

5의 배수인 경우 → 5로 나눈 값

3과 5의 배수인 경우 → 5로 나눈 값

3과 5 모두 배수가 아닌 경우 → 규칙 이용

n	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
봉지개수	1	-1	1	2	-1	2	3	2	3	4	3	4	3	4	5	4	5	4	5	6	5	6	5
n / 5	0	0	1	1	1	1	1	2	2	2	2	2	3	3	3	3	3	4	4	4	4	4	5
n % 5	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0

이를 통해 도출한, 규칙은 아래와 같다!!

n % 5 == 0 → n // 5

• n % 5 == 1 → n // 5 + 1
• n % 5 == 2 → n // 5 + 2
• n % 5 == 3 → n // 5 + 1
• n % 5 == 4 → n // 5 + 2

🚩My submission

n = int(input())

if n == 4 or n == 7:
    print(-1)

elif n % 5 == 0:
    print(n // 5)

elif n % 5 == 1 or n % 5 == 3:
    print(n //5 + 1)

elif n % 5 == 2 or n % 5 == 4:
    print(n // 5 + 2)

Time complexity : $O(1)$, Space Complexity: $O(1)$

🚩Others submission

1. 수학적 접근 2

n = int(input())

if n % 5 == 0:  # 5으로 나눠떨어질 때
    print(n // 5)
else:
    p = 0
    while n > 0:
        n -= 3
        p += 1
        if n % 5 == 0:  # 3kg과 5kg를 조합해서 담을 수 있을 때
            p += n // 5
            print(p)
            break
        elif n == 1 or n == 2:  # 설탕 봉지만으로 나눌 수 없을 때
            print(-1)
            break
        elif n == 0:  # 3으로 나눠떨어질 때
            print(p)
            break

Time complexity : $O(n)$, Space Complexity: $O(1)$

1. dp

N킬로그램까지 작은 숫자부터… 각각 가장 적은 양의 봉지를 저장해두면… 해당 값보다 3, 5 큰 위치에서 이전 값을 재사용할 수 있다.

import sys

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

arr = [5001] * (N+5)
arr[3] = arr[5] = 1

for i in range(6, N+1):
    arr[i] = min(arr[i-3], arr[i-5]) + 1

print(arr[N] if arr[N] < 5001 else -1)

• arr 배열은 N킬로그램일 때, 각각 가장 적은 양의 봉지를 담을 용도로 사용된다.
  • 최소 값 구해야하기 때문에 N의 범위보다 하나 큰 값이 “5001”을 값으로 지정한다.
  • index 3, 5에는 각각 1개의 봉지를 사용하고 최초의 값으로 이용하기 위해 “1”을 대입한다.
  • 배열의 크기를 “N+5”로 잡은 이유는… N의 값이 5보다 작은 경우 Index Out of Range 오류를 잡기 위해서다.
• 배열이 5와 같거나 보다 작은 경우는 이미 결과가 저장되어있기 때문에 for문의 range는 6부터 시작한다.
  • 6부터는 해당 위치보다 “-3”, “-5”의 위치 중 작은 값을 갖고와서 1을 더하면 해당 위치에서 가장 적은 양의 봉지를 구할 수 있다.
• N킬로그램을 만들 수 없으면 arr배열값이 5000보다 크기 때문에 치환해서 -1을 반환한다.

Time complexity : $O(n)$, Space Complexity: $O(n)$

💡TIL

• 나름 규칙 찾아서 단순하게 코드를 짜보았지만, dp로도 충분히 풀 수 있는 문제이다. 그런데 저렇게 if문으로도 코드가 가능하여 O(1) 시간복잡도인데, 굳이 반복문 돌고 리스트에 저장하며 시간복잡도, 공간복잡도를 높이는 건 아닌 것 같아 수학적으로 접근해보았다
• 역시 이런 문제는 ‘규칙’을 찾는 게 중요한 것 같다!!