[ DP - 2839 ] 설탕 배달(C++)

---

접근법

Dynamic Programming의 가장 쉬운 문제이다.

직관적인 접근이 가능한데, 우리가 원하는 것은 3a+5b = Inupt을 만족하는 a,b에 대하여 a+b가 최소가 되는 경우를 찾고싶은 것이다. 또한, 만들 수 없는 조합일 때는 결과가 -1이야 하는것을 명심하면 된다.

 

단순히 a 혹은 b 만으로 Input을 나타낼 수 있는 경우도 고려해야 하기 때문에 2중 for 문에서 해당 조건만 고려하면 쉽게 접근 가능하다. 또한, 3a+5b = Input을 만족하는 a,b에 대해서 Result를 처음에 -1로 설정하고 -1인 경우는 그냥 a+b를 Result로, -1이 아닌 경우 기존 Result와 a+b 중 작은 값을 Result로 설정하면 된다.

---

정답

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int32_t s32_Result = -1, s32_Input, s32_Three, s32_Five;

	cin >> s32_Input;

	for (s32_Three = 0; 3 * s32_Three <= s32_Input; s32_Three++)
	{
		for (s32_Five = 0; 5 * s32_Five <= s32_Input; s32_Five++)
		{
			if (3 * s32_Three + 5 * s32_Five == s32_Input)
			{
				if (s32_Result == -1)
					s32_Result = s32_Three + s32_Five;
				else
					s32_Result = min(s32_Result, s32_Three + s32_Five);
			}
		}
	}

	printf("%d\n", s32_Result);

	return 0;
}