[210426][백준/BOJ] 2839번 설탕 배달

문제

입출력

풀이

dp를 이용해서 문제를 풀 수 있다.

i 킬로그램 배달을 해야할때 필요한 봉지의 개수가 d[i] 일때
d[i] = min(d[i-3] + 1, d[i-5] + 1) 이다.
또한 최소값을 구하는 문제이므로 d 배열을 큰 값으로 초기화해줘야 한다.

코드

#include <bits/stdc++.h>
using namespace std;

int d[5002];

int dp(int n)
{
	fill(d, d + n + 1, 999999);
	d[3] = 1;
	d[5] = 1;

	for (int i = 6; i <= n; ++i)
		d[i] = min(d[i - 3] + 1, d[i - 5] + 1);
	return d[n];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	if (dp(n) >= 999999) cout << -1;
	else cout << dp(n);
}