백준 14501번 퇴사 C/C++ 풀이

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

동적계획법으로 풀었다.

 

배낭 알고리즘을 응용해서 풀었다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;

FILE* in = fopen("input.txt", "r");

#define MAX 15

int n;
int time[MAX];
int pay[MAX];
int cache[MAX+1][MAX * 1000];

int dp(int idx, int cost) {
	//메모이제이션
	if (cache[idx][cost] != 0)
		return cache[idx][cost];
	if (idx == n)
		return cost;
	if (idx + time[idx] <= n)
		return cache[idx][cost] = max(dp(idx + time[idx], cost + pay[idx]), dp(idx + 1, cost));
	else
		return cache[idx][cost] = dp(idx + 1, cost);
}

int main() {
	fscanf(in, "%d", &n);
	for (int i = 0; i < n; i++)
		fscanf(in, "%d %d", &time[i], &pay[i]);
	printf("%d", dp(0, 0));
	return 0;
}