백준 14501 퇴사

/*

최대 수익, 선택 날짜

/*

1. 해당 알바 실행 시 마쳤을 때 보수와 시행 안했을 때 보수를 비교하여 큰 쪽을 선택

1-1). alba[시작일+하는기간] = max(alba[시작일] + 보수, alba[시작일+하는기간]);

뽑아서 끝난 일 이후로 큰 값을 저장한다.

1-2). 알바를 마치는 일정이 퇴사날(N+1)이면 시행하지 않는다.

*/

#include <cstdio>

using namespace std;

void quick(int left, int right);

int N; // 1<= N <= 15

int alba[1010][2] = { 0, }, selectedAlba[1010] = { 0, }, maxMoney[1010] = { 0, }; //maxMoney는 1번 index부터 저장하여 좀 복잡해 지고 있다.

void dp(){

for (int i = 0; i < N; i++){

int finAlbaDay = alba[i][0] + (i + 1);

//퇴사일 보다 클 경우

if (finAlbaDay>(N + 1)){ continue; }

maxMoney[finAlbaDay] = maxMoney[finAlbaDay] > maxMoney[i + 1] + alba[i][1] ? maxMoney[finAlbaDay] : maxMoney[i + 1] + alba[i][1];

for (int j = finAlbaDay; j <= N + 1; j++){ // 해당 값이 뒤에 저장된 값보다 클 경우 뒷 값들을 전부 덮어 쓴다.

if (maxMoney[j] < maxMoney[finAlbaDay]) maxMoney[j] = maxMoney[finAlbaDay];

}

}

}

int main()

{

scanf("%d", &N);

for (int i = 0; i < N; i++){

scanf("%d %d", &alba[i][0], &alba[i][1]);

}

//quick(0, N - 1);

dp();

/*for (int i = 0; i < N; i++){

printf("%d %d\n", alba[i][0], alba[i][1]);

}*/

/*for (int i = 1; i <= N; i++){

printf("%4d",maxMoney[i]);

}*/

printf("%d\n", maxMoney[N + 1]);

return 0;

}

//알바가 일별로 하나씩 들어오는 경우가 아니고 한번에 들어오는 경우라면 정렬해서 하여야한다. 즉 이 문제에서는 필요없다.

void quick(int left, int right){

int i, j, s, t[2];

if (left < right){

i = left - 1, j = right + 1;

s = alba[(left + right) / 2][0];

while (true){

while (alba[--j][0] > s);

while (alba[++i][0] < s);

if (i >= j){ break; }

t[0] = alba[i][0]; t[1] = alba[i][1];

alba[i][0] = alba[j][0]; alba[i][1] = alba[j][1];

alba[j][0] = t[0]; alba[j][1] = t[1];

}

quick(left, i - 1);

quick(j + 1, right);

}

}