[C++] 백준 14501번 퇴사

next = i + arr[0][i];
if (next > n + 1) {
	DP[i] = DP[i + 1];
}
else {
	DP[i] = max(DP[i + 1], DP[next] + arr[1][i]);
}

 

다이나믹 프로그래밍 문제입니다.

 

n일동안 각 x일 걸리는 상담이 y라는 비용을 얻을때

가장 많이 비용을 얻은 값을 찾는 문제입니다.

 

마지막날 부터 각 최대값을 계산합니다.

1. n날 < 현재 날 + 상담 날

  n+1날의 최대값을 가져옵니다.

2. n날 >= 현재날 + 상담 날

  1) n+1날의 최대값과 

  2) 상담을 진행했을때 날짜의 최대값 + 현재 날짜 상담값

  1), 2) 중 큰 값을 현재날의 최대값에 넣습니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int arr[2][20];
int DP[20];

int main(int argc, char *argv[])
{
   int next;
   int value;
   int n;
   cin >> n;

   for (int i = 0; i <= n; ++i) {
      arr[0][i] = 0;
      arr[1][i] = 0;
   }

   for (int i = 1; i <= n; ++i) {
      cin >> arr[0][i];
      cin >> arr[1][i];
   }

   for (int i = n; i > 0; --i) {
      next = i + arr[0][i];
      if (next > n + 1) {
         DP[i] = DP[i + 1];
      }
      else {
         DP[i] = max(DP[i + 1], DP[next] + arr[1][i]);
      }
   }
   
   cout << DP[1] << endl;
   return 0;
}