[ baekjoon ] #14501 퇴사

백준 #14501 퇴사

문제 요약

---

• N+1일째 되는 날 퇴사하기 위해 남은 N일 동안 최대한 많은 상담을 하려고 한다.
• 상담을 완료하는 데 걸리는 기간 Ti, 상담을 했을 때 받을 수 있는 금액 Pi로 이루어짐
• 백준이가 얻을 수 있는 최대 수익 구하기 !

💡Idea

1. 해당 날까지의 최대 수익을 어떻게 구할까?
   • 이중 for를 사용해 해당 날까지의 최대 수익 구하자
     → 비효율적이라고 판단
   • 최대값을 저장해두는 변수를 하나 생성하자 !
2. 총 최대 수익을 어떻게 구할까?
   → 해당 날까지 얻은 수익 + 해당 날짜의 상담이 끝났을 때 얻는 이익을 비교해서 넣어주자 !

[ SourceCode ]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, max_pay = 0;
    cin >> N;
    vector <int> T(N+1), P(N+1);
    for(int i=0; i<N; i++) {
        cin >> T[i] >> P[i];
    }

    vector <int> dp(N+1);
    for(int i=0; i<=N; i++) {
        dp[i] = max(max_pay, dp[i]);
        if(i + T[i] <= N) {
            dp[i + T[i]] = max(dp[i] + P[i], dp[i + T[i]]);
        }
        max_pay = max(dp[i], max_pay);
    }

    cout << max_pay;
   
    return 0;
}

Feedback

---

1. 처음에 dp를 0부터 N-1까지 구하였다. (점화식은 제대로 세웠으나 범위 설정을 잘못함)
   → 이 경우 무조건 dp[N]이 구해지지 않는다.
   → max값과 dp[N]을 비교하거나 N까지 구하면 된다 !
2. dp는 문제가 어렵거나 코드가 복잡하지 않지만 어렵다 ㅠㅠ
   → 많이 풀어보면서 점화식을 세워보자 !