[백준/C++] 2839번 : 설탕 배달 (Greedy 연습)

설탕 배달

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 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

---

주어진 설탕 kg을 5kg과 3kg으로 나누어 최소한의 설탕 봉지를 가져가야 하는 문제다.

문제를 처음 보면 5kg 봉지를 최대한 많이 가져간 뒤, 5kg가 안되는 설탕은 3kg 봉지로 가져가면 되겠다고 생각했다.

접근은 쉬웠지만 효율적인 알고리즘으로 작성하기까진 생각보다 시간이 걸렸다.

 

#include <iostream>
#include <string>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;

	int cnt = 0;
	while(N > 0)
	{
		if(N % 5 == 0)
		{
			cnt += (N / 5);
			cout << cnt;
			return 0;
		}
		N -= 3;
		cnt++;
	}
	if (N == 0)
		cout << cnt;
	else
		cout << "-1";
	return 0;
}

 

입력받은 설탕 봉지 kg을 5로 나눠진다면 N/5만큼을 Count에 더한 뒤 출력하면 된다. 

반면 5로 나눠지지 않는다면, 5kg 봉지에 안담기는 설탕들이 존재한다는 뜻이므로, 3kg 설탕 봉지로 나누어서 가져가야 하므로 3kg씩 빼주고, 3kg 봉지를 하나 가져간 만큼 Count를 1 증가시킨다.

 

3kg 봉지를 계속 빼면서 남은 설탕이 0보다 작아졌는데도, 0으로 떨어지지않고 음수가 나온다면 5kg나 3kg로 나누어서 가져갈 수 없으므로 -1을 출력한다.

 

또한 3kg 봉지를 계속 빼면서 남은 설탕이 0이 되어 while문을 탈출하면 N == 0 일땐 3kg 봉지 만으로 설탕을 잘 가져갔기 때문에 cnt를 출력해주었다.

 

이 문제는 부분부분 코드를 고치고 테스트케이스를 다시 돌려보면 맞았던것도 또 틀리고, 틀렸던게 맞으면 다른게 틀리고 변화가 많았다.

코드를 변경하고 꼭 테스트케이스를 다시 처음부터 체크해봐야겠다. (사실 프로그래머스는 자동으로 이걸 해주는데..)

---

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달