[코드트리] 외주 수익 최대화하기 (삼성 SW 역량테스트 2017 상반기 오전 2번)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/max-of-outsourcing-profit

이후 설명 및 입/출력은 링크 참고

 

외주 수익 최대화하기 문제 풀이는 BOJ 14501 : 퇴사와 같다.

#include <stdio.h>

#define MAX (20+10)

int T;
int N;
int time[MAX];
int profit[MAX];
int answer;

void input()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d %d", &time[i], &profit[i]);
}

void DFS(int start, int sum)
{
	if (start + time[start] > N)
	{
		if (start + time[start] == N + 1) sum += profit[start];

		if (answer < sum) answer = sum;

		return;
	}

	for (int i = start + time[start]; i <= N; i++) DFS(i, sum + profit[start]);
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();
		answer = 0;

		for (int i = 1; i <= N; i++) DFS(i, 0);

		printf("%d\n", answer);
	}

	return 0;
}