[백준 2839] 설탕 배달

글에 개요

백준 알고리즘 2839번 "설탕 배달" 문제입니다.

백준 알고리즘 분류에서 '구현'에 있는 문제입니다. 순서대로 푸는 과정에서 난이도는 쉽지만 코드를 어떻게 하면 간결하게 짜면 좋을지에 대해 고민하기 좋은 문제인 것 같습니다.

저는 처음에 5 킬로그램 묶음으로 배달하는 갯수를 조절해서 풀었지만 코드가 복잡해졌습니다. 이에 어떻게 하면 좀 더 로직을 간단하게 할 수 있을지 고민해본 결과, 아래와 같이 해결하니 코드가 간편해졌습니다.

역시나... 먼저 해결할 아이디어를 먼저 고민해보고 푸는 것이 순서인 것 같습니다.

[백준 2839] 설탕 배달: https://www.acmicpc.net/problem/2839

참고할 글

1. http://brenden.tistory.com/40 ([백준 2577] 숫자의 개수 - 구현 문제)

핵심 내용

1. 설탕봉지를 3 킬로그램으로 배달하는 것이 최대값인 것을 인지하고 풀어야 됩니다.
2. 설탕봉지를 5 킬로그램 묶음으로 배달이 가능하면 이것이 최솟값이기 때문에 바로 반복문을 탈출해 주면됩니다.
3. 결과적으로 3 과 5 킬로그램의 묶음으로 배달이 불가능할 경우 -1을 출력해주면 됩니다. (처음 입력한 총량이 음수가 되었을 때를 따져주면 됩니다.) 

해결 방법

1. nThree라는 3킬로그램으로 배달할 갯수를 카운트해줄 변수를 선언합니다.
2. 11 line : 설탕봉지를 5 킬로그램으로 배달이 가능하지 않고 잔여 설탕배달 총량이 양수일 때 반복문을 계속 진행합니다.
3. 3 킬로그램 묶음을 하나씩 선택하는 과정을 반복합니다. 이는 5킬로그램으로 배달한 정수를 만들기 위한 과정입니다.
4. 15 line : 결국 3과 5의 조합으로 배달이 불가능할 경우 -1을 출력해주며, 이 외의 상황일 때는 3킬로그램 배달 묶음과 5 킬로그램 배달 묶음의 합을 출력해주면 됩니다.

백준 참고 내용

설탕 배달 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	48970	12142	9938	27.283%

문제

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

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

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

입력

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

출력

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

예제 입력 1 

18

예제 출력 1 

4

예제 입력 2 

4

예제 출력 2 

-1

예제 입력 3 

6

예제 출력 3 

2

예제 입력 4 

9

예제 출력 4 

3

예제 입력 5 

11

예제 출력 5 

3