Baekjoon 14501번: 퇴사

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

Q. 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 T_i와 상담을 했을 때 받을 수 있는 금액 P_i로 이루어져 있다.
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

전형적인 동적계획법 (DP) 문제다. 각 날짜를 기준으로 최대 수익 값을 계속 찾으면서 배열의 끝까지 도달하면 된다.
상담비용을 시작일에 선불로 다 받는다고 가정할 때, 1일에 상담을 진행할 경우 당일까지 총 이윤은 10원이다.
1일차에 상담을 시작해 버렸다면 2일차엔 상담을 진행할 수 없고 만약 1일차에 쉬었고 2일차 상담을 진행할 경우 20원이다.
4일차에선 1일차에 상담을 진행했을 경우에도 상담이 끝났으므로 새 상담을 진행 가능하다. 이윤은 10+20=30원이 된다.
5일차는 4일차 상담이 하루짜리이므로 바로 진행가능하다. 즉 30+15=45원이며, 6일차와 7일차 상담은 퇴사일까지의 시간이 부족해 받을 수 없으므로 최댓값이 45원이 되는 것이다.

`// https://www.acmicpc.net/problem/14501 Baekjoon No.14501 퇴사
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  int n;
  cin >> n;
  int t[n+1]; // j일자 상담을 마치는 데 필요한 시간 배열
  int p[n+1]; // j일차 상담의 보수 배열
  int dp[n+1]; // i일까지의 최댓값을 담을 배열
  for(int i = 1; i <= n; i++) {
    cin >> t[i] >> p[i];
    dp[i] = p[i];
  }

  for(int i = 2; i <= n; i++) { // i일까지를 기준으로...
    for(int j = 1; j < i; j++) { // i일 이전 j일까지의 최대 누적 보수 검사
      if(i-j >= t[j]) { // j일에 받은 상담이 다 끝났다면...
        dp[i] = max(p[i]+dp[j], dp[i]);
// i일에 상담을 받았을 경우는 둘 중 하나로 나뉜다.
// 1. 이전 j일까지의 상담이 다 끝나고 새 상담을 받는 경우
// 2. i일의 상담이 첫 상담인 경우
// 둘 중 더 큰 값이 i일의 최대 보수이다.
      }
    }
  }

  int max = 0;

  for(int i = 1; i <= n; i++) {
    if (i + t[i] <= n + 1) {
//마지막으로 각 날짜의 dp배열 값을 싹 검사. 퇴사일 이후까지 잡힌 상담이면 안됨 
      if (max < dp[i]) {
        max = dp[i];
      }
    }
  }
  cout << max;
}`