[C/C++] 백준 - 1663번 : 최고의 팀 만들기

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

1633번: 최고의 팀 만들기

문제

꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플레이어의 흑,백 능력치는 각각 1부터 100까지의 정수로 주어진다. 대회가 진행되는 동안 플레이어는 흑, 백 중 한 가지만으로 참여를 해야하며 팀의 전체 능력치는 흑 플레이어의 능력치를 합한것과 백 플레이어의 능력치를 합한것을 모두 더한 값이다. 어떻게 하면 꿍 협회는 가능한 높은 능력치의 팀을 만들수 있을까.

 

동적계획법으로 해결이 가능한 문제이다.

흑 15명 / 백 15명을 맞춰 총 30명을 맞춰야한다.

그렇다면 선택지는 총 3개가 존재한다.

 

1. 현재 흑 플레이어 한 명 선택

2. 현재 백 플레이어 한 명 선택

3. 아무도 선택하지 않고 다음 플레이어로 넘어가기

 

위 경우의 수를 저장해주면서 메모이제이션을 적용시켜준다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000007
#define endl '\n'

using namespace std;

int N = 0;
int player[2][1007];
int cache[1007][33][33];

void input() {
	while (1) {
		if (cin.eof()) break;
		cin >> player[0][N] >> player[1][N];
		N++;
	}
}

int choice(int count, int white, int black, int index) {
	if (count == 30) return 0;
	if (index == N) return -INF;
	int& ret = cache[index][white][black];
	if (ret != -1) return ret;
	ret = 0;
	ret = choice(count, white, black, index + 1);
	if (white < 15) ret = max(ret, choice(count + 1, white + 1, black, index + 1) + player[0][index]);
	if (black < 15) ret = max(ret, choice(count + 1, white, black + 1, index + 1) + player[1][index]);
	return ret;
}

int solution() {
	int answer = 0;
	for (int i = 0; i < N - 30; i++) {
		memset(cache, -1, sizeof(cache));
		answer = max(answer, choice(0, 0, 0, i));
	}
	return answer;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}