[백준 14501] 퇴사 (C#, C++) - soo:bak

문제 링크

14501번 - 퇴사

설명

N일 동안 매일 하나씩 상담 일정이 잡혀 있고, 각 상담에는 소요 기간과 수익이 있습니다.

퇴사일 전까지 겹치지 않게 상담을 선택해서 얻을 수 있는 최대 수익을 구하는 문제입니다.

접근법

뒤에서부터 거꾸로 생각하면 간단합니다.

예를 들어 5일에 3일짜리 상담이 있다면, 이 상담을 하면 8일에 끝납니다.

퇴사일이 6일이라면 이 상담은 할 수 없고, 그냥 다음 날로 넘어가는 수밖에 없습니다.

반대로 상담이 퇴사일 안에 끝난다면, 상담을 해서 수익을 얻는 것과 건너뛰는 것 중 더 나은 쪽을 선택합니다.

이렇게 마지막 날부터 첫째 날까지 거꾸로 계산하면, 첫째 날에서 시작했을 때의 최대 수익을 구할 수 있습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var t = new int[n + 2];
    var p = new int[n + 2];
    for (var i = 1; i <= n; i++) {
      var parts = Console.ReadLine()!.Split();
      t[i] = int.Parse(parts[0]);
      p[i] = int.Parse(parts[1]);
    }

    var dp = new int[n + 2];
    for (var i = n; i >= 1; i--) {
      var end = i + t[i];
      if (end <= n + 1) dp[i] = Math.Max(dp[i + 1], dp[end] + p[i]);
      else dp[i] = dp[i + 1];
    }

    Console.WriteLine(dp[1]);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi t(n + 2, 0), p(n + 2, 0), dp(n + 2, 0);
  for (int i = 1; i <= n; i++) cin >> t[i] >> p[i];

  for (int i = n; i >= 1; i--) {
    int end = i + t[i];
    if (end <= n + 1) dp[i] = max(dp[i + 1], dp[end] + p[i]);
    else dp[i] = dp[i + 1];
  }

  cout << dp[1] << "\n";

  return 0;
}