[백준] 설탕 2839번 (c++)

출처 : 2839번: 설탕 배달 (acmicpc.net)

2839번: 설탕 배달

풀이 방법

dp 문제로 쉬운 문제였다. 

재귀로 n을 입력받아 min(f(n-5), f(n-3)) + 1을 해주면 된다 

기저 조건으론 n이 음수이면 INF(매우 큰 값)를 리턴해서 선택되지 못하게 n이 0이면 0을 리턴해서 끝났다는 것을 알려 주었다

마지막 출력부분에선 f(n)이 INF보다 크면 -1을 리턴 아니면 f(n)의 리턴 값을 리턴해 주면 된다

#include <iostream>
#include <algorithm>
#include <memory.h> 
#include <vector>

using namespace std;

int dp[5001];
const int INF = 987654321;
int f(int n) {	
	// 기저 사례	
	if (n < 0) return INF;
	if (n == 0) return 0;
	// dp table 이용
	int& ret = dp[n];
	if (ret != -1) return ret;	
	ret = 0;
	ret = min(f(n - 5), f(n - 3)) + 1;	
	return ret;


}
int main(void) {
	memset(dp, -1, sizeof(dp));
	int N;
	cin >> N;
	int ans = f(N);
	if (ans > INF) cout << -1;
	else cout << ans;
	return 0;
}