[백준] 2898 (C++)

문제는 여기

설명

설탕을 정확하게 N 킬로그램을 배달해야 하고, 3kg과 5kg 봉지가 있다. 이때 최대한 적은 갯수의 봉지를 가져가며, 3kg와 5kg 봉지로 가져갈 수 없을 때엔 -1을 출력한다.

알고리즘

다이나믹 프로그래밍을 사용합니다. 다이나믹 프로그래밍이란, 재귀호출 등을 이용해 하나하나 계산해나갈 수 있는 문제를 효율적으로(=빠르게) 풀기 위해 고안된 프로그래밍 기법입니다.
cache로 사용될 배열을 만든 후, 앞에서부터 구하고자 하는 값까지 배열을 채워나갑니다. 이때 앞에서 구한 값을 사용하여, 점화식의 모양새로 이후의 값들을 채워나가게 됩니다.
즉 특정 값들에 대하여 일반화가 가능한 점화식이 적용되는 경우에 다이나믹 프로그래밍을 사용하면 됩니다.
해당 문제의 경우에는, 도출해볼 수 있는 일반화된 점화식은 다음과 같습니다.

1. DP[i] = min(DP[i-3]+1, DP[i-5]+1) => 단, DP[i-3]과 DP[i-5]가 -1이 아니다.
2. DP[i-3]과 DP[i-5]가 모두 -1인 경우에는, DP[i] 역시 -1가 됩니다.

이를 구하기 위해 차근차근 DP[3]부터 구하되, -1가 아닌 값들만을 추려보면
DP[3] = 1
DP[5] = 1
DP[6] = 2 = DP[6-3]+1
DP[8] = 2 = min(DP[8-3]+1, DP[8-5]+1)
DP[9] = 3 = DP[9-3]+1
DP[10] = 2 = DP[10-5]+1
DP[11] = 3 = min(DP[11-5]+1, DP[11-3]+1)
위처럼 일정한 규칙을 갖고 있음을 알 수 있습니다.

코드

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int DP[5001];

int makeN(int sugar)
{
	memset(DP, 0, sizeof(DP));
	DP[3] = DP[5] = 1;
	for (int i = 6; i <= sugar; i++)
	{
		if (DP[i - 3] && DP[i - 5]) DP[i] = min(DP[i - 3] + 1, DP[i - 5] + 1);
		else if (DP[i - 3] && !DP[i - 5]) DP[i] = DP[i - 3]+1;
		else if (!DP[i - 3] && DP[i - 5]) DP[i] = DP[i - 5]+1;
		else DP[i] = 0;
	}
	if (DP[sugar] == 0) DP[sugar] = -1;
	return DP[sugar];
}

int main()
{
	int s;
	cin >> s;
	cout << makeN(s);
}