84. 휴가 [DFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

 

풀이 

- DFS 문제

- 최대비용을 얻도록 여행날짜까지 상담을 진행해야 한다. 

- 가지를 뻗을 때 상담 한다 vs 안한다 두가지로 나눈다.

- 만약 현재 L+T[L] 즉 현재 날짜의 상담을 완료 한 후의 날짜가 n+1을 넘지 않고 마무리 가능하면 => DFS(L+T[L], sum+P[L])

- L+T[L]이 여행날짜를 넘기면 상담을 하지 않고 다음날짜로 이동하면서  sum을 그대로 넘긴다 => DFS(L+1, sum)

- L==n+1일때 sum과 res를 비교해서 res<sum이면 res=sum으로 교체한다.

 

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int n, res=-2147000000;
vector<int> T, P; //날짜 & 수익
//84. 휴가

void DFS(int L, int sum){
    if(L==n+1){
        if(sum>res) res=sum;
    }else{
        if(L+T[L]<=n+1) DFS(L+T[L], sum+P[L]); //n+1일까지 마무리 가능 => 상담 한다
        DFS(L+1, sum); //안하고 다음날로 넘어감
    }
}

int main(){
    int a, b;
    scanf("%d", &n); //상담 횟수
    T.push_back(0);
    P.push_back(0);
    for(int i=0;i<n;i++){
        scanf("%d %d", &a, &b);
        T.push_back(a);
        P.push_back(b);
    }
    DFS(1,0);
    printf("%d\n", res);
    return 0;
}