[C++] 설탕 배달 : 2839번

문제

 

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

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

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

---

문제 해석

 

3키로와 5키로를 합하여 입력받은 N 을 만드는

3키로와 5키로의 합의 최소 갯수를 구하면 된다.

 

조건으로는, 3과 5의 정수배로 만들 수 없는 수는 -1을 출력한다.

 

문제를 풀기 위해서는 범위를 생각해야한다.

입력받은 무게가 18kg라고 가정했을 때,

3과 5의 각각 최대 갯수는

3으로만 만들었을 때, 18 / 3 = 6

5로만 만들었을 때는 18 / 5 = 3(나누어 떨어지지 않음)

 

그럼 각각의 반복문은    0부터 6    /    0부터 3  까지만 돌아야한다는 것을 알 수 있다.

이것을 활용해 문제를 풀 수 있다.

 

 

---

풀이

#include <iostream>
using namespace std;

#define MAX 5000 / 3 // 범위는 5000까지 이므로 나올 수 있는 봉지의 최대 갯수

int main()
{
	int kg; int min = MAX; // 무게, 최소 봉지 수 저장할 공간
	cin >> kg;

	for (int three = 0; three <= kg / 3; three++) // 3키로 짜리는 무게 / 3 만큼이 최대
	{
		for (int five = 0; five <= kg / 5; five++) // 5키로는 무게 / 5
		{
			if ((3 * three + 5 * five) == kg) // 3키로 5키로의 정수배 합이 정확히 무게일 경우
			{
				if (min > three + five) // 최소 값이면
				{
					min = three + five; // 최소값 저장
				}
			}
		}
	}
	if (min == MAX) // 변화없이 min이 그대로라면
	{
		cout << -1;	// 아무것도 나누어 떨어지지 않는다.
	}
	else // 최소값이 생겼으면
	{
		cout << min; // 출력
	}
}

three 라는 3kg의 봉지가 0개부터 ~ kg / 3 개 만큼 돌고

five 라는 5kg 의 봉지는 0개부터 ~ kg / 5 개 만큼 돈다.

 

min 이라는 최소값에 최소 갯수의 합을 저장하는데,

맨 처음의 min 은 5000 / 3으로 지정했다.

문제에서의 최대 무게 입력 범위는 5000kg 이므로, 5000kg 를 최대한 많은 봉지로 만들면

5000 / 3 이상의 숫자가 나온다. 따라서 min 을 5000 / 3 으로 define 하였다.