BOJ 14501.퇴사

입력

1 : N(날짜)
2 ~ N+1 : T_i(기간) P_i(금액)

주의사항

1) STL에 정의돼있는 함수 이름과 중복되지 않게 변수 선언하기

구현방식: DFS 기반 완전탐색

1) DAY 1 ~ DAY N까지 DFS(배열 접근 0 ~ N-1)
2) DFS 함수
-종료 조건
: 탐색하려는 day가 N이상인가?(배열 접근 고려)

-재귀호출
①탐색하는 day와 해당 상담기간의 합이 N이하일 때, cur_price 가산
②탐색하는 day와 해당 상담기간의 합부터 N까지 재귀함수 호출

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int maximum = 0;
vector <int> T, P;
int N, T_tmp, P_tmp;

void dfs(int day, int cur_price) {
	if (day >= N) {
		if (cur_price > maximum)
			maximum = cur_price;
		return;
	}

	else {
		if(day + T[day] <= N)
			cur_price += P[day];

		for (int i = day + T[day]; i <= N; i++)
			dfs(i, cur_price);
	}
}

int main(void) {
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d %d", &T_tmp, &P_tmp);
		T.push_back(T_tmp);
		P.push_back(P_tmp);
	}
	
	for (int i = 0; i < N;i++)
		dfs(i, 0);

	printf("%d\n", maximum);
}