백준 15486번 퇴사2 C/C++ 풀이

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

15486번: 퇴사 2

 

이 역시도 DP 문제

 

1부터 n까지 순회하면서 현재까지의 최댓값을 저장해둔다.

 

dp[n]은 n일까지 일했을 때 얻을 수 있는 최대 수익으로

 

i번째 날에 들렸을 때, 현재까지 얻을 수 있는 최댓값과 그 날에 저장된 값을 비교하여 갱신하여 주고,

 

i번째 날에 일했을 때 얻을 수 있는 최대 수익을 i번째 일했을 때 수익을 얻는 날(i + 해당 일의 소요 날짜) dp 배열에 값을 갱신하여 준다.

 

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

#define MAX 1500001

using namespace std;

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

int n;
int time[MAX];
int money[MAX];
int cache[MAX];
int curr_max;


//cache[n]은 n일까지 일했을 때의 최대 수익
void dp(int idx) {
	//현재까지의 최대 수익과 cache[n] 값을 비교해준 뒤 갱신
	curr_max = max(curr_max, cache[idx]);
    //idx가 n을 넘어가면 런타임 오류가 뜨기 때문에 조건문에서 선제적으로 처리
    //idx+time[idx]는 n번째의 갱신하기 때문에 등호를 붙여준다.
	if(idx < n && idx + time[idx] <= n)
		cache[idx + time[idx]] = max(curr_max + money[idx], cache[idx + time[idx]]);
    // 갱신
	cache[idx] = curr_max;
	return;
}

int main() {
	fscanf(in, "%d", &n);
	for (int i = 0; i < n; i++)
	{
		fscanf(in, "%d %d", &time[i], &money[i]);
	}
    // 0부터 n까지 순회
	for (int i = 0; i <= n; i++)
		dp(i);
	printf("%d", cache[n]);
}