BOJ 14501번: 퇴사

문제

문제 바로가기> BOJ 14501번: 퇴사

14501번: 퇴사

 

풀이

dp를 이용해서, 뒤에서부터 거꾸로 오면서, 백준이가 얻을 수 있는 최대 수익을 구해 줄 수 있다.

 

`dp[i]` : i+1 ~ N일 기간, 백준이가 얻을 수 있는 최대 수익

 

#include<iostream>
#include<vector>
#define MAX 16
using namespace std;

int N;
int dp[MAX];
pair<int, int> consult[MAX]; // time, pay

void input(){
    cin >> N;
    
    int t, p;
    for(int i=0; i<N; i++){
        cin >> t >> p;
        consult[i] = {t, p};
    }
}

void solution(){
    for(int day=N-1; day>=0; day--){
        if(day + consult[day].first > N) dp[day] = dp[day+1]; // 회사에 없어서 상담이 불가능한 경우
        else dp[day] = max(dp[day+1], dp[day+consult[day].first]+consult[day].second);
        
    } cout << dp[0]; // 백준이가 얻을 수 있는 최대 수익
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}