[알고리즘] 백준 14501 c++

문제 링크

14501번: 퇴사

틀린이유

• 뒤에서부터 생각하지 못했음

why? 반복되어 사용되는 게 있어 DP 문제라 생각했고, DP에서 최대는 누적이니까 당연히 앞에서부터 누적된다고 생각함.
but, 문제는 앞에서부터 했을 때 어디까지 가능한지 체크해야되고 이에 DP를 사용하는 게 어려움 -> 뒤에서 하도록 생각을 바꿔야 했음

문제 분석

문제

• 상담을 완료하는 데 걸리는 시간 : T_i
• 상담을 했을 때 받을 수 있는 금액 : P_i
• 구하는 것: 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익은?

입력

• N일 : 1≤ N ≤ 15
• 1≤ T_i ≤ 5, 1≤ P_i ≤ 1,000

해결방안

• i 번째 일에 상담을 할 수 있냐의 여부는 T(상담 시간)에 달려있음
• 상담 시간이 긴 것을 앞에서 했으면, 뒤에서 못 함
• 그런데, 앞에서부터 시작하면 뒤로 갈 때 마다 상담을 할 수 있냐 여부를 계속 체크 해줘야함 (i가 T를 넘기는 순간까지)
• 그래서 뒤에서부터 상담 가능 여부를 체크하고, 현재를 선택하는 게 나을지 i 다음을 선택하는 게 나을 지 판단해야함

코드

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

int t[17];
int p[17];
int d[17];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    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] <= n+1) { // 선택 가능
            // 선택했을 경우, 선택 안했을 경우
            d[i] = max(p[i] + d[i+t[i]], d[i+1]);
        } else { // 선택 불가능 
            d[i] = d[i+1];
        }
    }
    cout << *max_element(d+1, d+n+1);

    return 0;
}