[C++] DFS - 휴가(삼성 SW)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<pair<int, int>> a;
int res = -2147000000;
void DFS(int v, int sum){
    if(v == N+1){
        if(sum > res) res = sum;
    }
    else{
        if(v+a[v].first<= N+1)//한다면 날짜를 더해줌 더해주는데 8일을 넘어가지 않아야함.
            DFS(v+a[v].first, sum+a[v].second);
        
        DFS(v+1,sum);//안한다면 바로 다음칸
    }
}

int main() {
    int T,P;
    scanf("%d",&N);
    
    a.push_back(make_pair(0, 0));
    for(int i = 1; i <= N; i++){
        scanf("%d %d", &T, &P);
        a.push_back(make_pair(T, P));
    }
    
    DFS(1,0);
    
    printf("%d",res);
    return 0;
}

• 최선의 값을 구해야하므로 BFS라고 생각할 수 있다.
• 하지만, 코드 시뮬레이션을 하다보면 넓게 탐색하기 보단 깊게 탐색하는게 더 낫다는 걸 알 수 있다. 아무래도 상담 날짜가 정해져있고 상담 날짜 이후의 상담만 예약할 수 있다보니, 깊게 탐색하는게 더 낫다라고 직관적으로 생각하게 되는 것 같다. 

 

DFS로 푼다고하면 생각보다 되게 간단한 문제이지만, 사실 고려해야할 부분이 있다.

1. 만약 7일차에 상담일이 2일이라고한다면, 8일에도 상담을 해버리게 된다. 따라서, 상담일이 8일 이후에도 적용된다면 걸러야한다.(입력 값에 너무 치중하다보면 이런 것을 고려하지 못하게된다) 만약 이걸 고려하지 않았다면 재귀를 아래처럼 짯을 것이다.

void DFS(int v, int sum){
    if(v > N+1){ //8일 이후에 상담받는 것도 고려하게된다.
        if(sum > res) res = sum;
    }
    else{
        ...
        8일 이후값 거르지 않고 바로 재귀
    }
}

2. 이런 문제들은 순서가 정해져있다. 만약 3일차 상담을 받았다면 1일차와 2일차는 굳이 고려할 필요가 없다. 따라서 7개의 가지를 만들 필요가 없다.(순서가 정해져있다.) 따라서, 상담을 한다와 안한다로 두개의 가지를 뻗어나가는 것이 더 유리하다. 만약 이걸 고려하지 않았다면 재귀를 아래처럼 짯을 것이다.

void DFS(int v, int sum){
    if(v > N+1){
        if(sum > res) res = sum;
    }
    else{
        for(int i = vec[v].first + v; i <= N; i++){
        	DFS(i, vec[v].second + vec[i].second);
        }
    }
}

만약 7일차에 상담일 수가 이틀을 넘어간다면 for문이 성립조차되지 않는다
너무 입력값에만 충실한 나머지 이런식으로 코드를 생각하게 되었다.

다음부턴 이런 실수를 하지 않겠다!

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard