[BaekJoon/백준] 14501번 퇴사2

퇴사 1번 문제(https://hevton.tistory.com/586)는 완전탐색으로 풀었다고 봐야 한다.

O(N^2)의 알고리즘이니까,, 150만 x 150만은 퇴사2에서 시간초과가 나올 수 밖에 없다.

 

DP를 사용해야 한다. 근데 나 DP 왤케 못하지??? 이 문제 두시간 붙잡고 못풀어서 해설 찾아봤다.

 

근데 문제 해설도 이해가 잘 안된다. 해설만 두시간 더 붙잡았다.

나 오늘 진짜 코테 망하더니 멘탈 나갔나보다. 진짜 화가 많이 나긴 했다.. 인터넷 진짜

 

 

다들 하향식으로만 풀던데, 이유는 왤까.. 상향식은 아예 불가능한 것인가.. 의문이 들어서 막 찾아봤는데

별다른 해설이 없었다. 일단 지금은 못해보겠다. 정말 피곤해 죽겠고 아무것도 안잡힌다.

 

5시간을 붙잡았는데도 안되는거면, 오늘은 쉬어야겠지..

#include <iostream>
#include <vector>
#define MAX(a, b) ((a >= b) ? a : b)

using namespace std;

int DP[1500002];
int N;
vector<pair<int,int>> v;



int main() {
    
    int A, B;
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        
        cin >> A >> B;
        
        v.push_back({A,B});
    }
    
    
    for(int i = N - 1; i >= 0; i--) {
        
        
        if(i + v[i].first <= N) {
            
            DP[i] = MAX(DP[i + 1], v[i].second + DP[i + v[i].first]);
            
        } else
            DP[i] = DP[i + 1];
        
    }
    
    cout << DP[0] << "\n";
    
    
}

 

참고 : https://j2wooooo.tistory.com/42

 

 

+ 상향식 풀이를 딱 하나 봤는데, MAX 변수를 따로 유지하면서 사용했다.

 

상향식 풀이를 하면, 1일에 3일이 걸리는 일을 택하면 4일부터 ~~ N일까지 영향이 되는데 그거를 다 체크해주기 어렵고, 마지막 최종 MAX값도 DP[N]같은 곳이 아닌, 어디로 튈지 모르는 곳이니까 하향식 풀이보다 깔끔한 풀이는 아닌 것 같고

하향식 풀이를 하면 그거를 체크할 필요가 없으니까 깔끔해서 쓰는 듯 하다.

(잠시 숨돌리니까 곧바로 이유가 생각이 나네...)