[삼성SW역량테스트/DFS] 14501번 퇴사

여태 삼성 문제 4개를 풀었는데 4개 모두다 DFS문제다 삼성은 DFS를 정말 좋아하는듯

문제 풀이

먼저 1일에 있는 스케쥴을 선택한 경우 5일이 걸리므로 6일 부터 10일 사이에 있는 스케쥴을 그다음 스케쥴로 고를 수 있다.

고를 수 있는 스케쥴의 모든 경우의 수 를 살펴보자.

1일,6일,7일 -> 80

1일,6일,8일 -> 90

2,6,7일 -> 70

2,6,8->80

3,6,7->60

3,6,8->70

4,6,7,->50

4,6,8->60

5,6,7->40

5,6,8->50

6,7,8->30

7 -> 20

8 -> 30

위의 경우를 빼고는 스케쥴을 선택 할 수 없고 이 모든 경우의 수 중에서 가장 큰 이익을 얻을수 있는건 1일 6일 8일에 있는 스케쥴을 선택해서 총 90의 가치를 얻는 것이다.

이런식으로 모든 경우의 수를 탐색해야 하는 문제는 DFS로 풀면 손쉽게 풀 수 있다.

소스코드 

#include <iostream>

#include <algorithm>

using namespace std;

int n;

int input[2][16];

int result;

int dp[16];

int DFS(int index){

    if(index+input[0][index] >= n+2) return 0;

    int rt = input[1][index];

    int MAX = 0;

    for(int i=index+input[0][index]; i<=n; i++)

    {

        MAX = max(MAX,DFS(i));

    }

    return MAX+rt;

}

int main(){

    cin>>n;

    for(int i=1; i<=n; i++)

        for(int j=0; j<2; j++)

            cin>>input[j][i];

    int maxx = 0 ;

    for(int i=1; i<=n; i++)

        maxx = max(maxx,DFS(i));

    

    cout << maxx <<endl;

    return 0;

}