[BaekJoon/백준] 14501번 퇴사

 

DP로 풀어야 하나, BFS로 풀어야 하나 고민이 많았다.

 

그나마 둘 중에 자신있는 DP로 풀었는데

그래도 깔끔하게 풀었던 건 아닌 것 같다..

 

 

DP[i] = i번째까지 선택을 고려했을 때, 최대 이익.

 

i 번째에 하는 일은,

1. i 번째를 선택할 수 있는지를 고려하고
2. i 보다 작은 날짜 중에서, i번째를 고려할 수 있는 누적값이 있는지 본다

 

 

약간 냅색유형스럽게 풀었다.

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

// DP냐, BFS냐 => DP를 선택했다.

using namespace std;

int N;

vector<pair<int, int>> v;

int DP[16]; // v에 대한 DP를 다룰 배열

//DP[i] => i일 까지 선택할 수 있는 최대

int MAX; // MAX 값


int main() {
    
    int A, B;
    
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        
        cin >> A >> B;
        
        v.push_back({A, B});
        
    }
    
    // insertion sort처럼,, 이전까지의 값들에서 현재랑 엮일 수 있는 것들을 뽑는다.
    // 또한 현재 값 자체도 선택될 수 있는지를 NOW를 통해 지정한다.
    
    for(int i = 0; i < N; i++) {
        
        // 현재 것을 포함할 수 있는지 여부
        int NOW = (v[i].first + i) <= N ? v[i].second : 0;
        
        // 유별난 케이스 ㅜ i가 0일때, 아래 반복문을 진행하지 않으므로 여기서 지정
        // 대신 for i문 밖에서 지정해주면, 예외가 있음. NOW를 기준으로 다뤄줘야 하기 때문..!
        if(i == 0)
            DP[i] = NOW;
        
        for(int j = 0; j < i; j++) {
            
            if( v[j].first + j <= i ) { // 이전 것에 누적할 수 있다면
                
                // 이전 것에서 선택하여 최대를 선택.
                DP[i] = MAX((DP[j]+NOW), DP[i]);
                
            } else {
                // 이전 것에서 누적될 수 없다면, NOW와 DP[i] 중에 최대를 선택.
                DP[i] = MAX(DP[i], NOW);
            }
        }
    }
    
    for(int i = 0; i < N; i++) {
        
        if(MAX < DP[i])
            MAX = DP[i];
    }
    
    cout << MAX << "\n";
    

    
}

다른 분들의 풀이도 참고해봤더니,, 내 코드가 한없이 부족하게 느껴졌다.

좀 더 노력하자//

 

 

 

주의할 점은.. 아래와 같다.

처음에 '틀렸습니다' 떠서 참고했다.

 

https://www.acmicpc.net/board/view/86462

글 읽기 - 91%에서 틀리셨다면..