BOJ 14501번: 퇴사

문제 설명

상담 완료하는데 걸리는 시간 T와 상담했을 때 받을 수 있는 금액 P가 주어졌을 때, 남은 N일 동안 받을 수 있는 최대 금액 구하기

🔗 문제 링크

핵심 아이디어

• 오늘 날짜부터 퇴사 전까지를 역순으로 생각
• d[i]를 i번째 날부터 퇴사일까지 벌 수 있는 최대 수익으로 두기
• 퇴사 전까지 상담할 수 있는지 확인
• 상담했을 경우: p[i] + d[i + t[i]] (오늘 수익 + 남은 날들의 최대 수익)
• 상담 안했을 경우: d[i+1] (남은 날들의 최대 수익)

코드

#include <bits/stdc++.h>
using namespace std;
int n;
int t[20];
int p[20];
int d[20];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    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)
            d[i] = max(d[i+1], p[i] + d[i + t[i]]);
        else
            d[i] = d[i+1];
    }
    
    cout << d[1];
}

놓친 부분

• 선택이 미래에 영향을 미치면 역순으로 생각해보기
• "d[i]를 i번째 날부터 퇴사일까지 벌 수 있는 최대 수익으로 두기"