[백준 14501][C++] 퇴사 (Silver 4)

[문제보기]

 14501. 퇴사

14501번: 퇴사

 

[풀이과정]

문제를 보자마자 다이내믹 프로그램(dp)으로 풀어야겠다고 생각했다.

이중 포문을 사용하여 코드를 짰는데, 2가지 경우의 수를 사용하여 dp의 갱신을 진행하였다.

1. j 번째 날까지 일을 안 하고 i 번째 날까지 온 경우의 점화식 max(dp[i], dp[j])

2. j 번째 날에서 data[j]. second 기간 동안 일을 하여 돈을 받을 경우 j+data[j].second 하여 i 번째

   날에 돈을 받는 경우의 점화식 max(dp[i], dp[j]+data[j].second)

이렇게 세웠다. 

그리고 문제에서는 n <= 15인데 배열을 16으로 만들었는데 이는 딱 n번째 날까지 일을 하여 돈을 받을 수 있으므로

16으로 정하였다.

[소스코드]

#include <iostream>
using namespace std;
int n;
pair<int, int> data[16];
int dp[16] = {0};
int ans = 0;

int main(){
    cin >> n;
    int t, p;
    for(int i=0; i<n; i++){
        cin >> t >> p;
        data[i].first = t;
        data[i].second = p;
    }

    for(int i=0; i<=n; i++){
        for(int j=0; j<i; j++){
            dp[i] = max(dp[i], dp[j]);

            if(j+data[j].first == i){
                dp[i] = max(dp[i], dp[j] + data[j].second);
            }
        }
    }

    for(int i=0; i<=n; i++)
        ans = max(ans, dp[i]);

    cout << ans <<"\n";

    return 0;
    
}

 

[풀이과정 중 실수한 부분]

요새 dp문제를 많이 풀어서 어떤 식으로 접근을 해야 될지는 감이 잡히고 있지만, 모든 조건에 대한 

점화식을 세우는 부분에서 조금 시간이 걸리고, 손으로 계산을 해봐야 식이 세워진다.