백준 1633번 최고의 팀 만들기 C/C++ 풀이

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

1633번: 최고의 팀 만들기

전형적인 동적계획법 문제.

 

재귀함수와 메모이제이션을 이용해서 문제를 풀었다.

 

#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;

FILE* in = fopen("input.txt", "r");

int white[1001];
int black[1001];
int cache[1001][16][16];
int n;

int dp(int w, int b, int now) {
	if (now == n)
		return 0;

	if (cache[now][w][b] != -1)
		return cache[now][w][b];

	int ret = 0;

	if (w > 0)
		ret = max(ret, dp(w - 1, b, now + 1) + white[now]);

	if (b > 0)
		ret = max(ret, dp(w, b - 1, now + 1) + black[now]);

	ret = max(ret, dp(w, b, now + 1));

	return cache[now][w][b] = ret;
}

int main() {
	int tmp_w; int tmp_b;

	memset(cache, -1, sizeof(cache));

	while (fscanf(in, "%d %d", &tmp_w, &tmp_b) > 0)
	{
		white[n] = tmp_w; black[n] = tmp_b;
		n++;
	}

	printf("%d", dp(15, 15, 0));

	return 0;
}