백준 14501 퇴사

문제

문제링크 : https://www.acmicpc.net/problem/14501

풀이전략

1. 제한시간은 2초이기에 충분히 완전탐색으로 풀수 있다.
2. DFS를 활용하여 해결하고, 모든 케이스 최대값을 찾는다.

코드

#include<bits/stdc++.h>

using namespace std;

#define mine

int N;
vector<pair<int, int> > a;
int res = -2147000000;

void DFS(int T, int P){
    if(T>=N){
        if(P>res) res = P;
    }
    else{

        if(T+a[T+1].first <= N){
                DFS(T+a[T+1].first, P+a[T+1].second);
        }
        DFS(T+1, P);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    int t1,t2;
    a.push_back(make_pair(-1,-1));
    for(int i=0; i<N; i++){
        cin >> t1 >> t2;
        a.push_back(make_pair(t1,t2));
    }
    DFS( 0, 0);
    cout << res << endl;
    return 0;
}

소감

시간이 충분하면 완전탐색만큼 확실한 방법은 없다.