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

해결 방법

삼성 기출 리스트를 풀다가 퇴사 문제를 풀었던 적이 있었다.
https://velog.io/@1eq0/BOJ-14501-퇴사
비슷할거라 생각하고 입력 범위를 봤는데

• N (1 ≤ N ≤ 1,500,000)
• 1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000

ㅎㅎ.. 2차원으로 풀 수 있을리가 없다. 1500000 x 1500000 ..?
어떻게 하면 1차원 배열 가지고 풀 수 있을까 생각해봤다.

점화식

dp[i]를 i일째 퇴사했을 때 받을 수 있는 금액의 최댓값으로 정했다.
그렇다면 답은 dp[N]에 담겨있을 것이다.

i : 1 ~N을 순회하며,

• i로부터 t[i]일 뒤인 nday에,
  현재 저장된 값과 i-1일까지 얻을 수 있는 금액의 최댓값 + p[i] 중 최댓값을 저장한다.
• 현재(i일)에 얻을 수 있는 금액도 갱신해준다.

따로 범위를 넘어가는 조건을 체크하지 않았기 때문에, 배열 범위를 넉넉하게 잡았다.

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long

const int n_ = 1500060;
int N;
int t[n_];
int p[n_];
int dp[n_];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin>>N;
	for(int i = 1; i<=N; i++){
		cin>>t[i]>>p[i];
  }

  for(int i = 1; i<=N; i++){
    int nday = i+t[i]-1;
    dp[nday] = max(dp[nday], dp[i-1]+p[i]);
    dp[i] = max(dp[i-1],dp[i]);
  }

  cout<<dp[N]<<"\n";
}

제출 결과