[백준 14501] 퇴사

0. 제목

• 백준 14501 퇴사
• BOJ 14501 퇴사
• C++ 14501 퇴사

---

1. 문제

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

---

2. 풀이

• dp방식을 사용하였으며 dp배열의 원소값을 0으로 모두 초기화 하고 시작하였다.
• 만약 일을 진행하는데 주어진 날보다 초과되면 dp[i+1] 값을 해주면 된다. 초기에 0으로 초기화해주었기 때문에 N이 초과되어도 0으로 갱신이 가능하다.
• 주어진 날 내에 끝낼 수 있다면 dp[i] = max(dp[i+T[i]] + P[i], dp[i+1]); 을 수행해준다.
• 위 점화식을 풀어 설명해보면 dp[i+T[i]]+P[i] 는 i번째 상담을 수행하면 T[i]일간 상담을 못하고 P[i]의 금액을 얻을 수 있고, dp[i+1]은 i번째 상담을 수행하지 않으면 그 전단계(역으로 가기 때문에 전단계라고 표현함)인 dp[i+1]으로 갱신되게 된다.
• 그렇게 마지막 단계인 dp[1] 이 얻을 수 있는 최대 수익이 된다. 

---

3. 코드

#include <iostream>
using namespace std;
 
int N;
int T[16];
int P[16];
int dp[16];
 
int main(int argc, const char * argv[]) {
    cin >> N;
 
    for(int i = 1; i <= N; i++){
        cin >> T[i] >> P[i];
    }
    
    for(int i = N; i >= 1; i--){
        if(i + T[i] - 1 > N){
            dp[i] = dp[i + 1];
            continue;
        }
        
        dp[i] = max(dp[i + T[i]] + P[i], dp[i+1]);
    }
    
    cout << dp[1] <<'\n';
    
    return 0;
}