[백준] 14501번 : 퇴사

문제

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

14501번: 퇴사

 

 

주안점

최대 이익 찾기 => 부르트 포스, 그리디, 동적 프로그래밍

부르트 포스로 찾을 수도 있으나 효율을 위해서 동적 프로그래밍이 적당하다.

 

 

구조

dp함수 : parameter로 넘어온 index에서 얻을 수 있는 최대 금액이 리턴된다.

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int n,t,p;
vector<int> day,pay;
int a[19][19];

int dp(int idx){
	if(idx >= n) return 0;
	int &ret = *a[idx];
	if(ret != -1) return ret;

    ret = 0;
    if(idx+day[idx] > n) {
        ret = max(ret, dp(idx+1));
    } else {
        ret = max(dp(idx+1), dp(idx+day[idx])+pay[idx]);
    }

	return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	cin>>n;
	for(int i=0; i<n; i++){
		cin>>t>>p;
		day.push_back(t);
		pay.push_back(p);
	}
	memset(a, -1, sizeof(a));
	cout<<dp(0)<<"\n";
}