[BOJ] 2839번: 설탕 배달

✏️ 문제

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

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

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

 

🤖 입출력 예시

 

💡 풀이

이코테 책으로 그리디 알고리즘을 공부하고 있는 기세를 이어 백준에서 그리디 유형으로 분류된 문제를 풀어보는 중이다.

 

아이디어 1️⃣

그리디 알고리즘으로 풀기 위해 처음 떠올린 아이디어는 아래와 같다.

 

ⅰ. N이 5의 배수인 경우 → 답은 N//5

ⅱ. N이 3의 배수인 경우 → 답은 N//3

ⅲ. N이 3의 배수도 아니고 5의 배수도 아닌 경우 → N이 7, 8, 11, ...

 

첫 번째와 두 번째 케이스는 답이 명확하기 때문에 '세 번째 케이스를 잘 처리할 수 있느냐'가 이 문제의 핵심이라고 생각했다.

 

그런데 세 번째 케이스에 대해서 계속 생각해보니까

 

1) N에서 5를 뺀 값(최대한 N을 작게 만들어나가는 게 중요하다고 판단)이 3이나 5로 나누어지는지 체크

2) 3이나 5를 뺀 과정에서 무조건 하나의 설탕을 옮긴 거니까 답에 +1

 

여기까지의 과정에서부터 허점이 보였다.

 

예를 들어, 8이나 11은 3과 5를 잘 조합하면 답이 나오는데 7은 어떻게 해도 저 값을 만들 수 없기 때문에 -1이 나와야 한다.  그런데 계산을 멈추는 조건을 어떻게 걸어줘야 하지?가 가장 큰 고민이었고, 이것 말고도 다양한 의문이 들었으므로 내가 생각한 로직이 뭔가 잘못됐구나! 싶었다.

 

아이디어 2️⃣

두 번째 아이디어는 '5kg짜리 설탕을 무조건 먼저 고려하고 남은 무게를 3kg로 채우는 것'이다.

 

import sys

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

answer = -1

for i in range(N//5, -1, -1):
    remainder = N-(i*5)
    
    if remainder%3 == 0:
        answer = i+(remainder//3)
        break   # 답이 나왔기 때문에 계속 계산할 필요가 없음

print(answer)

 

 

반복문 범위를 아예 최대로 쓸 수 있는 5kg 봉지의 수에 맞춰놓고 거기서 하나씩 줄여가면서 값을 확인하는 방식이다. 5kg 봉지를 쓴 만큼 빼준 후 3으로 나눴을 때 나눠 떨어진다면 이미 답이 구해진 것이기 때문에 break를 걸어 탈출해준다.

 

이 때 8번 라인에서 remainder라는 추가적인 변수를 사용하지 않고 N -= (i*5)를 쓸 경우 답이 이상하게 나오는 문제가 있었고 챗지피티의 도움을 받았다.

 

이런 데서 코딩의 기본기가 나오는 게 아닐까.. 난 아직도 갈 길이 한참 멀다 ⭐