[c++] 휴가(DFS활용)

#include <iostream>
#include <vector>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int ch[100], n, sum=0, res=-2147000000;
vector<int> map[20];
vector<int> T;
vector<int> P;
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]);
		else DFS(L+1, sum);
	}
}
int main() {
	freopen("input.txt", "rt", stdin);
	int a, b;
	scanf("%d", &n);
	T.push_back(0);
	P.push_back(0);
	for(int i=1; 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;
}

DFS를 활용해서 선택된 L의 합을 구한 후 그중 최소값을 구하는 문제이다.

이전 최소비용 문제와 비슷한 문제이나 다른 점은 본 문제는 앞으로 전진만 하기 때문에 

for문을 통해서 처음부터 다시 점검하면서 DFS를 진행하지 않아도 된다.

반면에 최소비용 문제는 각각의 노드가 연결되어 있고 앞으로만 전진하고 있지 않기 때문에 

for문을 통해 ch배열에 체크를 해주어야 한다.

 

- 최소비용 문제

soyeondev.tistory.com/205

[c++] 최소비용(DFS: 인접행렬)

 

내가 처음 DFS문제를 접할 때 먼저 생각하는 것은 DFS가 받는 파라미터인데 

지금까지는 L로 받고 레벨단위로 구성해서 해당 레벨에서 더 가지를 뻗어나갈 수 있는 경우의 수를 

for문을 통해 점검했었다. 그러면서 이전레벨에서 이미 지나온 수는 ch배열에 체크를 하고 

다시 가지 못하게 만들었는데

 

이 문제에서는 T배열에 입력된 수만큼 앞으로만 전진하면서 마지막에 L이 n+1이 되는지만 확인하면 되므로

체크를 할 필요가 없다. 따라서 DFS의 if else 구문의 else부분에서 먼저 L+T[L] 이 n+1을 넘지 않는지 먼저 체크한 후 넘지 않는다면 다음 위치로 옮겨가는 작업을 한다.

만약 L+T[L] 이 n+1을 넘는다면 선택되지 않고 한칸만 움직인 위치에서 다시 체크를 시작한다.