[성실코딩 12일차] 백준 #15486 퇴사 2 / DP

14501 퇴사랑 같은 문제인데 퇴사하려는 일 N+1이 15 -> 1,500,000 으로 증가하였다. 

시간 초과될까봐 너무 걱정했음 ㅜㅜ

!시간 초과 걱정되서 수정한 부분!

DP 1차원 배열 채울 때, 시간초과 날까봐 걱정되서 수정한 부분은

이전 코드에서는, DP[i] = i에 잡혀있는 상담을 했을 때의 최대금액

현재 코드에서는, DP[i] = i에 잡혀있는 상담을 했을 때의 최대금액과 DP[i+1~N] 중에 최대금액

차이점은 i에 잡혀있는 상담을 했을 때의 금액을 계산하고, 그 이후 날짜중 최대금액을 찾기위해 i+1~ N까지 검사했어야했지만

지금은 DP[i+1]에 값하고만 비교하면됨. 

반복문을 한차례 없앨 수 있음

그리고 이전 코드에서의 정답은  DP를 다 채운 후에, DP에서 for문 돌아서 DP[i]증 가장 큰 값,

현재 코드에서의 정답은 DP를 다 채운 후에, 항상 DP[0]임.

문제풀이

구현코드

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

using namespace std;

int n; // 배열 사이즈
int arr[2][1500001];

int populateDP() {

	vector<int> DP(n + 1);
	for (int i = n; i > 0; i--) {
		int new_one;
		if (i + arr[0][i] - 1 <= n) { // i일에 잡혀있는 상담을 할 수 있다면
			new_one = arr[1][i];
			if(i + arr[0][i] <=n){ // i일 상담 후, 상담하여 받을 수 있는 최대 금액
				new_one += DP[i + arr[0][i]];
			}

			if (i+1<=n) 
			{
				DP[i] = max(new_one, DP[i + 1]);
			}
			else {
				DP[i] = new_one;
			}
		}                            // i일에 잡혀있는 상담을 할 수 없다면
		else {
			if (i+1<=n) { // i+1일이후에 잡혀있는 상담들을 해서 받을 수 있는 최대금액으로 
				DP[i] = DP[i + 1];
			}
		}
	}

	return DP[1];
}

int main() {

	scanf("%d",&n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d",&arr[0][i],&arr[1][i]);
	}

	printf("%d", populateDP());
	return 0;
}