[백준 15486] 퇴사 2

www.acmicpc.net/problem/15486

15486번: 퇴사 2

dp 사용문제인데 까다롭당..

 

dp[n]은 n일까지 일했을 때 받을 수 있는 최대 금액이다. n일에 일한건 n일에 못받는다. 최소 n+1일에 받을 수 있음

 

문제의 핵심은 일을 끝마쳤을 때의 날짜의 금액 dp[arr[i][0] + i ]값을 업데이트 해주는 것이다.

하지만 dp[arr[i][0] + i ] = max(dp[arr[i][0] + i], dp[i] + arr[i][1])을 해주면 틀리는데 그 이유는 전날 일을 안하고 지나갔을 때의 최댓값 업데이트가 안되어 있기 때문이다.

무슨 의미냐면 예시 4의 경우 

dp[8]이 90이 되어야 하는데 저거 하나만 따지면 30이다.

dp[6]이 dp[7]만 업데이트하기 때문

 

따라서 dp[i+1] = max(dp[i], dp[i+1])을 해줘야 한다.

dp[i]에서 일을 하지 않으면 dp[i+1]은 dp[i]에서 받는 비용을 그대로 받기 때문

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그래서 코드는 이렇다.

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

using namespace std;

int arr[1500001][2];
int dp[1500001];
int main(void)
{
  int n;
  scanf("%d", &n);

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

  for (int i = 1; i <= n; i++)
  {
    int idx = arr[i][0] + i;
    dp[idx] = max(dp[idx], dp[i] + arr[i][1]);
    dp[i + 1] = max(dp[i], dp[i + 1]);
  }
  printf("%d\n", dp[n + 1]);
  return 0;
}