<C/C++> BOJ 14501: 퇴사

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

14501번: 퇴사

 

예전에 풀었던 문제인데 지금 다시보니 DFS로도 풀 수 있을 것 같네요!

#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 15
int N; // N+1일에 퇴사
int T[MAXN + 5]; // 상담 완료하는데 걸리는 기간
int P[MAXN + 5]; // 상담 했을 때 받을 수 있는 금액
int C[MAXN + 5];
int sol;

void InputData(void) {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> T[i] >> P[i];
	}
}

int max(int a, int b) {
	return a > b ? a : b;
}

void Solve(void) {
	// 하려는 날짜보다 같거나 더 빨리 끝나면서 수익이 더 많으면 그쪽으로 옮김
	for (int i = 1; i <= N; i++) {
		if (i + T[i] <= N + 1) { // 일했을 때
			C[i + T[i]] = max(C[i + T[i]], C[i] + P[i]);
			sol = max(sol, C[i + T[i]]);
		}
		// 일 안했을 때
		C[i + 1] = max(C[i + 1], C[i]);
		sol = max(sol, C[i + 1]);
	}
	cout << sol << endl;
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	InputData();
	Solve();
	return 0;
}