[PS][완전탐색][N자리 K진수]/[BOJ][15486][퇴사2]

boj15486.cpp

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int n = 0;
int dp[1500010];
int input[1500010][2];

int recur(int curr) {
	if (curr == n) return 0;
	if (dp[curr] != -1) return dp[curr];
	if (curr + input[curr][0] > n) return dp[curr] = recur(curr + 1);
	return dp[curr] = max(recur(curr + input[curr][0]) + input[curr][1], recur(curr + 1));
}



int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input[i][0] >> input[i][1];
	}
	memset(dp, -1, sizeof(dp));
	/*for (int i = 0; i <= n; i++) {
		cout << dp[i] << " ";
	}*/
	cout << recur(0) << "\n";

	/*for (int i = 0; i <= n; i++) {
		cout << dp[i] << " ";
	}*/
	return 0;
}

//하향식 설계

1. dp에 절대 들어갈 수 없는 -1을 넣어둔다. 연산 결과가 0이 되는 경우도 있을 수 있다.
2. dp에 저장된 값이 있으면 그 값을 return 한다.
3. curr의 일을 선택할 수 있는 경우, 없는 경우를 나눈다.
4. curr의 일을 하는 경우, 안하는 경우를 나눈다.

//상향식 설계

#include <iostream>
#include <algorithm>
using namespace std;
int n = 0;
int dp[1500010];
int a, b;
int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio("false");
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		//i번째 날짜의 일을 선택하는 경우
		if (i + a <= n) {
			dp[i + a] = max(dp[i+a], dp[i] + b);
		}
		//선택안하는 경우
		dp[i + 1] = max(dp[i], dp[i + 1]);
	}
	cout << dp[n] << "\n";
	return 0;
}