백준 14501_퇴사(C++)

https://www.acmicpc.net/problem/14501

14501번: 퇴사

[문제 풀이]

문제의 해결법은 DFS인 거 같다.
DP로 풀려고 하였지만 풀고 보니 메모제이션을 이용하지 않았기 때문에 DFS인 걸로 보인다.

점화식
solution(pos + 1), solution(pos + arr[0][pos]) + arr[1][pos] 을 이용하여 풀었다.

매 단계마다 i번째 날에 일할 것인지 안 할 것인지를 봐주면서 DFS로 파고드는 방법이다. 

[코드]

#include<iostream>
#include<algorithm>

using namespace std;

#define INF -987654321;

int N;
int arr[2][15];
int dp[15] = { -1, };

int solution(int pos) {

	if (pos == N)
		return 0;
	if (pos > N)
		return INF;

	return max(solution(pos + 1), solution(pos + arr[0][pos]) + arr[1][pos]);
	
}

int main() {

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d %d", &arr[0][i], &arr[1][i]);
	}

	printf("%d", solution(0));

	return 0;
}