[백준OJ] 1633번 최고의 팀 만들기

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

1633번: 최고의 팀 만들기

---

 

 

풀이

모든 선수를 탐색하며, 만약 현재까지 백팀에 15명이 안찼을때 백팀에 넣은경우, 흑팀에 15명이 안찼을때 흑팀에 넣은경우, 어느 팀에도 넣지 않은경우 3가지와 현재상태중 최댓값을 넣어주면된다.

이때 DP의 Memoization을 이용해서 시간을 단축시켜준다.

또한 문제에서 주어진 입출력의 종료조건이 따로 주어지지 않아서 scanf로 받고, EOF가 아닐때까지로 조건을 주었다.

 

코드

#include<iostream>
#include<algorithm>
#include<memory.h>//memset
#include<vector>
#include<cstdio>
#define _CRT_SECURE_NO_WARNINGS.
using namespace std;

vector<pair<int, int>> v;
int dp[1001][16][16];

int dfs(int white, int black, int ind) {
	if (ind == v.size()) {
		return 0;//end point
	}

	if (dp[ind][white][black] != -1) {
		return dp[ind][white][black];//memoization
	}

	if (white <15) {
		//백 선택
		dp[ind][white][black] = max(dp[ind][white][black], v[ind].first+dfs(white+1,black,ind+1));
	}

	if (black <15) {
		//흑 선택
		dp[ind][white][black] = max(dp[ind][white][black], v[ind].second + dfs(white, black+1, ind + 1));
	}
	dp[ind][white][black] = max(dp[ind][white][black], dfs(white, black, ind + 1));//아무것도 선택x 계산 후 리턴
	return dp[ind][white][black];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int a, b;
	while (scanf("%d %d",&a,&b)!=EOF) {
		v.push_back({ a,b });
	}
	memset(dp, -1, sizeof(dp));

	cout << dfs(0,0, 0) << "\n";

	return 0;
}