[C] Algorithm : Backjoon 14501 퇴사

Baekjoon Problem 14501 is resignation. Please check the details and pictures of the problem in Baekjonn. For uncomplicated algorithmic problems, it is possible to code the problem right away, but it is possible to reduce trial and error by analyzing the problem and thinking about which functions and elements to solve the problem and organizing it.

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

Analysis of the problem requirements is as follows.

1. The date must be changed when the consultation was conducted and when the consultation was not conducted.
2. Calculate the number of all cases with or without counseling, and calculate the cost at that time.
3. Compare the costs in each case and calculate the maximum return.

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

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

The detailed requirements and analysis of the problem are as follows.

1. Implement date shift according to the presence or absence of consultation through the index.
2. The cost is passed within the function to calculate the total cost in some cases.
3. The number of all cases according to the presence or absence of consultation is implemented through a recursive function (in the code below, it is expressed as DFS).

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

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;
}