[백준] 15486번: 퇴사 2 (C++)

문제 링크

15486번: 퇴사 2

---

저번주에 트리를 공부하다가 트리DP라는 친구를 만났는데 참 만만치 않았습니다. 😂

그래서 DP를 공부해야겠다 생각했고, DP 관련해서 열심히 공부해보고자 이번 문제를 풀어보게 되었습니다!

풀이

N의 크기가 크기 때문에, DP를 이용해서 풀어야 합니다.

종만북(알고리즘 문제 해결 전략)에 의하면, N의 크기가 150만이면 \(O(N\log{N})\)정도에서 커버가 가능하다고 합니다.

다시말해, \(O(N\log{N})\)이하의 알고리즘에 의해 풀어야 하는데, 이는 이중 for문으로는 힘든 시간복잡도입니다.

따라서 DP를 사용해야 합니다. 문제를 다시 한번 살펴보면 다음과 같습니다.

1. N일 동안 최대한 많은 상담을 하면서 최대 수익을 얻도록 해야 합니다. = DP를 이용해라
2. N일 동안 일을 하면, 그 N일 사이에 있는 일은 하지 못합니다.

2번을 다른 시각으로 생각해봅시다. N일 동안 일을 하면 그만큼의 보수(T)를 받습니다. 그런데 보수는 언제 받을까요?

N일을 일한 이후에 받습니다. N일을 일한 이후는? N+1일입니다. 이 사실을 이용해서 다음과 같은 과정으로 DP를 풀면 되겠습니다.

1. 내가 벌은 돈(`money`)을 저장해 두고, 현재 벌 수 있는 돈과 비교해서 더 많은 가치가 있는 쪽을 택합니다.
2. 내가 벌은(벌 수 있는) 돈과 현재 벌 수 있는 기간의 N+1만큼의 돈을 비교해서 더 많은 가치가 있는 쪽을 택합니다.

풀이코드

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

#define endl "\n"

int dp[1500001];

void solve() {
  int n;
  cin >> n;
  
  int money = 0;
  for (int i = 1; i <= n; i++) {
    int t, p;
    cin >> t >> p;

    money = max(money, dp[i]);
    if (i + t > n + 1) continue;

    dp[i + t] = max(money + p, dp[i + t]);
  }

  cout << max(money, dp[n + 1]);
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

 

배운점

• DP를 복습할 수 있었습니다.
• 머리가 아픕니다...

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!