[코테/백준] Python 설탕 배달 - 2839번

성공 | 시도 11번

 

🔗 [백준] 2839번 설탕배달

2839 : [그리디 알고리즘] 설탕 배달(py)

---

문제 설명

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

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

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

---

문제 분석

- 봉지에는 3킬로그램 봉지와 5킬로그램 봉지가 있고 최대한 적은 봉지를 들고 가야 한다.

예)  18킬로그램 설탕 → 3킬로그램 봉지 6개 VS 5킬로그램 3개 & 3킬로그램 1개(총 4개)

- 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 가져가야할 봉지의 최소 개수를 구한다.

---

입력

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

---

출력

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

---

입력과 출력 예시

입력	출력
18	4
4	-1
6	2
9	3
11	3

 

 

🔗 [질문 게시판] 참고할만한 반례

---

Trial 

해당 문제를 풀면서 여러 시도를 했지만 그 중 기억에 남는 시도들을 정리하였다. 

 

Trial 1 

- 문제를 제대로 읽지 않아 잘못 접근했다.

- 문제를 보면 '정확하게 N킬로그램을 배달해야 하고 그게 안되면 -1을 출력'하라고 되어있다. 

- 나는 '정확하게'를 제대로 보지 못하고 그냥 '봉지의 최소 개수'에만 집중해서 문제를 풀었다. 

 

Trial 2

- 적은 봉지 개수를 얻기 위해서는 3 킬로그램 봉지보다 5 킬로그램 봉지에 초점을 맞춰야 한다는 것을 알았다. 그래서 그에 맞게 로직을 세웠고 문제에 주어진 입력과 출력값도 정확히 나온다는 것을 확인했다. 하지만 답안을 제출하면 오답이라고 판명되었다. 질문 게시판에서 반례 값을 찾아보게 되었고 그 결과, 대략 입력값이 25일 때부터 출력값이 다르게 나온다는 것을 확인하였다.

- '특정 입력값 이후에 왜 봉지의 개수가 다르게 출력될까?'에 대해 고민하였다. 여러 숫자들을 분석한 결과, 5의 배수를 뺄 때 작은 수부터 뺐기 때문에 문제가 생긴다는 것을 알게 되었다. 그래서 다음 시도(최종 소스)에서는 큰 5의 배수부터 거꾸로 빼는 로직으로 수정하였다. 

- 다양한 반례들이 필요하다는 것을 느꼈다. 

→ 🔗 [질문 게시판] 참고할만한 반례

 

[Trial 2에서 사용한 방식]

1) 18 킬로그램

	1	2	3
5 킬로그램	1개	2개	3개
3 킬로그램	X	X	1개

→ 18 킬로그램은 문제없이 4개로 출력된다. 

 

2) 25 킬로그램

	1	2	3	4	5
5 킬로그램	1개	2개	3개	4개	5개
3 킬로그램	X	5개	X	X	-

→ 원래라면 출력값이 5개로 나와야 하지만, 내가 작성한 코드에서는 7개로 출력된다. 

---

내 소스

n = int(input())
value = -1

if n % 5 == 0:
    value = n // 5
else :
    for i in range(n // 5, 0, -1):
        q = n - 5 * i
        if q % 3 == 0:
            value = i + q // 3
            break
if (value == -1) and (n % 3 == 0) :
    value = n // 3

print(value)

 

소스 설명

if n % 5 == 0:
    value = n // 5
else :
    for i in range(n // 5, 0, -1):
        q = n - 5 * i
        if q % 3 == 0:
            value = i + q // 3
            break

[4 - 11]

- 적은 봉지 개수를 갖기 위해서는 5 킬로그램 봉지를 먼저 사용해야 한다. 설탕 무게가 5의 배수라면 5 킬로그램 봉지를 사용하는 것이 낫기 때문에 5로 나눈 몫을 구한다.

- 설탕 무게가 5의 배수가 아니라면 설탕 무게에서 5의 배수를 뺀 나머지가 3의 배수인 경우를 찾는다. for 문은 설탕 무게를 5로 나눈 몫을 시작으로 1까지 1을 차감한다. 설탕 무게를 5로 나눈 몫을 사용하는 이유는 5가 큰 단위이기 때문에 최대치의 범위라고 생각했다. 또 Trial 2에서 느꼈던 것처럼 큰 5의 배수를 먼저 빼야 적은 봉지를 얻을 수 있다. 

- 5의 배수를 뺀 나머지가 3의 배수인 경우, value에는 5의 몫과 3의 몫을 더한 값이 담긴다. (이렇게 표현해도 되는지 모르겠다...) 반대로 5의 배수를 뺀 나머지가 3이 배수가 아닌 경우에는 value는 그대로 -1을 갖고 있는다.

 

if (value == -1) and (n % 3 == 0) :
    value = n // 3

[12 - 13] : 설탕 무게가 (1) 5의 배수도 아니고 (2) 5의 배수를 뺀 나머지가 3의 배수도 아닌 경우, 설탕 무게가 3의 배수인지 확인한다. 3의 배수라면 3을 나눈 몫을 value에 담고 3의 배수가 아니라면 value는 그대로 -1을 갖는다.

---

다른 코드 분석

- while 문을 사용하여 5의 배수가 될 때까지 설탕의 무게에서 3씩 빼가는 방식을 사용하였다. 

 

---

회고

해당 문제를 어떻게 풀어야 할 지 몰라서 고민도 많이 하고 시간도 많이 들였다. 여러 시도에도 잘 풀리지 않아서 '다른 사람의 답을 볼까'라는 충동이 몇 번 들었지만 꾹 참고 로직을 하나하나 손으로 그렸다. 그런 시도 끝에 결국 풀게 되었고 통쾌함을 느꼈다. 

if 문과 for 문 중첩을 간결하게 할 수 있는 방법을 고민해봐야 할 것 같다.  

---

Ref.

1. 문제 풀이 / https://ooyoung.tistory.com/81

---

* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀