[C] Backjoon 14501 퇴사

백준 14501번 문제는 퇴사이다. 문제에 대한 내용과 그림 등은 백준에서 직접 확인하길 바란다. 복잡하지 않은 알고리즘 문제에서는 바로 코딩을 해도 되지만, 문제를 분석하고 어떤 함수와 요소들을 활용하여 문제를 해결할지 고민하고 정리하는 것이 시행착오를 줄일 수 있다.

문제 요구 사항을 분석하면 아래와 같다.

1. 상담을 했을 때와 하지 않았을 때 날짜를 변경해야한다.
2. 상담 유무에 대한 모든 경우의 수를 구하고, 그때의 비용을 계산한다.
3. 매 경우의 비용을 비교하여 최대 수익을 계산한다.

문제 상세 요건 및 분석사항은 아래와 같다.

1. 상담 유무에 따른 날짜 이동을 인덱스를 통해 구현한다.
2. 비용이 함수 내에서 전달되어 경우에 따른 총 비용을 계산한다.
3. 상담 유무에 따른 모든 경우의 수는 재귀함수를 통해 구현한다 (아래 코드에서는 DFS로 표기한다).

#include <stdio.h>

int T[16];
int P[16];
int g_max=-999999;

void DFS(int v, int N, int psum) {
	if (v == N + 1) {
		if (g_max < psum) g_max = psum;
		return; 
	}
	if (v + T[v] <= N + 1) 	DFS(v + T[v], N, psum + P[v]);
	if (v + 1 <= N + 1) DFS(v + 1, N, psum);
}

int main() {
	int N;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &T[i], &P[i]);
	}
	DFS(1, N, 0);
	if (g_max == -999999) printf("0");
	else printf("%d", g_max);
	return 0;
}