[Brute Force - 재귀] 퇴사

예제 입력 1

7

3 10

5 20

1 10

1 20

2 15

4 40

2 200

예제 출력 1

45

예제 입력 2

10

1 1

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

1 10

예제 출력 2

55

예제 입력 3

10

5 10

5 9

5 8

5 7

5 6

5 10

5 9

5 8

5 7

5 6

예제 출력 3

20

예제 입력 4

10

5 50

4 40

3 30

2 20

1 10

1 10

2 20

3 30

4 40

5 50

예제 출력 4

90

 

 

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

 

[풀이1 : Brute Force]

#include <stdio.h>

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MAX_SIZE (16)

int T[MAX_SIZE];
int P[MAX_SIZE];

int N;
int maxResult = 0;

void go(int nowDay, int nowMoney)
{
	maxResult = MAX(maxResult, nowMoney);

	for (int i = nowDay; i <= N; i++)
	{
		if (i + T[i] > (N+1)) continue;

		go(i + T[i], nowMoney + P[i]);
	}
}

int main(void)
{
	scanf("%d", &N);
	
	for (int i = 1; i <= N; i++)
	{
		scanf("%d %d", &T[i], &P[i]);
	}

	go(1, 0);

	printf("%d\n", maxResult);

	return 0;
}

[풀이2 : 다이나믹 프로그래밍]

#include <stdio.h>

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MAX_SIZE (16)

int T[MAX_SIZE];
int P[MAX_SIZE];

int N;
int maxResult = 0;

int D[MAX_SIZE];

int main(void)
{
	scanf("%d", &N);
	
	for (int i = 1; i <= N; i++)
	{
		scanf("%d %d", &T[i], &P[i]);
	}


	for (int i = 1; i <= N; i++)
	{
		if (i + T[i] > N + 1) continue;
		D[i] = P[i];
		
		for (int j = 1; j <= i; j++)
		{
			if (j + T[j] <= i)
				D[i] = MAX(D[i], D[j] + P[i]);
		}
	}

	for (int i = 1; i <= N; i++)
		maxResult = MAX(maxResult, D[i]);

	printf("%d\n", maxResult);

	return 0;
}