백준 2839번: 설탕 배달

[문제 링크]

2839번: 설탕 배달

---

간단한 DP 문제였다.

상근이가 N킬로그램을 배달하는 봉지의 최소 갯수를 점화식으로 표현하면 다음과 같다.

result = 1 + min(dp(N-3), dp(N-5))

---

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int INF = 987654321;
int memo[5001];

int dp(int N) {
	if (N == 0) return 0;
	else if (N < 0) return INF;

	int& ret = memo[N];
	if (ret != -1)
		return ret;
	ret = INF;

	return ret = min(ret, 1 + min(dp(N - 3), dp(N - 5)));
}

int main(void) {
	memset(memo, -1, sizeof(memo));

	int N;
	cin >> N;
	
	int result = dp(N);
	cout << (result == INF ? -1 : result) << endl;

	return 0;
}