[백준] 2839설탕배달 c++

dp문제이다.

2중 for문을 통해서 풀어줬다.

3키로 봉지와 5키로 봉지와 조합을 해서 만들 수 있는 무게여야하고

최소의 개수의 봉지를 사용해야한다.

sugar[3]과 sugar[5]를 1로 초기화 해줬다.

해당 무게를 만들 수 있는 조합을 안에 있는 for문으로 다 검사해주어서 최소의 개수를 sugar[i]에 넣어주었다.

#include<iostream>
#include<algorithm>

using namespace std;

int sugar[5001];



int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < 5001; i++)
		sugar[i] = 5000;

	sugar[3] = 1;
	sugar[5] = 1;
	for (int i = 3; i <= n; i++)
	{
		for (int j = 3; j <= i; j++)
		{
			
			sugar[i] = min(sugar[j] + sugar[i - j],sugar[i]);
			
		}
	}
	if (sugar[n] == 5000)
		cout << -1;
	else
		cout << sugar[n];
}