[백준 14501번] 퇴사 (C++)

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

14501번: 퇴사

퇴사를 하기 전까지 최대 수익을 내야하는 문제이다.

실버3이지만 앞에서 미리 포스팅했던 포도주 시식이나 RGB거리 등 다른 Dp문제보다 더 애먹었다.

Dp 문제를 접하는 마인드로 일단 어떻게든 다 훑어야지 라고 생각하며 접근했는데...처음 2중for문으로 점화식을 짰는데...예외 상황이 너무 많아서 하나씩 예외처리를 하다보니까 코드가 Greedy하게 변했다.

결국 풀다가 시간이 너무 지나서 작성했던 코드 다지우고 담날에 새로 하자는 마인드로 그냥 잤다 ㅋㅋ

담날에 수업시간에 잠깐 봤는데 어떻게 탐색해야할지 새로운 아이디어가 떠올라서 했더니 바로통과...흠

하여튼 한번에 풀지 못했으니 많이 복기 해봐야겠다.

 

방법은 글로 표현하기엔 조금 어렵고, 코드를 보고 직접 손으로 따라가는게 더 이해가 더 쉬울 것이다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
int main(){
  ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
  int n; cin >> n;
  int dp[16];
  memset(dp,0,sizeof(dp));
  int* T = new int[n+1];
  int* P = new int[n+1];
  for(int i = 1; i < n+1; i++){
    cin >> T[i];
    cin >> P[i];
    if(i + T[i] <= n+1) dp[i] = P[i];
  }

  for(int i = 1; i < n+1; i++){
    for(int j = i + T[i]; j< n+1; j++){
      if((T[j] + j <= n+1) && (dp[j] < dp[i] + P[j])){
        dp[j] = dp[i] + P[j];
      }
    }
  }
  cout << *max_element(begin(dp), end(dp));
}

 

 

 

 

 

수많이 Dp를 그리디화 한 흔적...ㅋㅋ

AC를 받고 다른 사람들의 풀이를 보니까 Dp탐색을 뒤에서부터 하면 시간복잡도 n으로 해결할 수 있는거 같다.