백준 14501번. 퇴사(c++) / 그리디

여러가지 방법으로 구현해볼 수 있는 문제였다.

보니까 다들 dp, 그리디, 재귀 등 다양한 방법으로 풀었다.

 

[메인 로직]

1 | 2 | 3 | 4 ... | n-1 | n 까지 for문으로 탐색하면서

다음으로 (지금 날짜+걸리는 날)만큼 더한 날짜로 넘어가서

최대값을 찾는다.

 

아무래도 코드를 보면 더 이해가 잘 될 듯하다.

 

// 퇴사
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, days, cost;
vector<pair<int, int>> v;
int ans = 0;
 
void dfs(int day, int total)
{
    if(day>v.size()) return;
    ans = max(ans, total);
 
    for(int i=day; i<v.size(); i++){
        int days = v[i].first;
        int cost = v[i].second;
 
        dfs(i+days, total+cost);
    }
}
 
int main()
{
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>days>>cost;
        v.push_back(make_pair(days, cost));
    }
 
    for(int i=0; i<v.size(); i++){
        int days = v[i].first;
        int cost = v[i].second;
        
        dfs(i+days, cost);
    }
 
    cout<<ans<<"\n";
    return 0;
}