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

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

 

3차원 dp배열을 만들어서 문제를 해결하였다. dp[k][i][j]의 의미는 k번 인덱스까지 i개의 백, j개의 흑을 뽑았을 때의 최대값 이다. 팀을 선택할 수 있는 경우는 백을 뽑는경우, 흑을 뽑는경우, 아무도 뽑지 않는 경우 셋으로 나눌 수 있다.

따라서 점화식은

dp[k][i][j] = max (dp[k - 1][i - 1][j] + k번의 백의 점수, dp[k - 1][i][j - 1] + k번의 흑의 점수, dp[k - 1][i][j]) 로 나타낼 수 있다.

 

처음에 cin.eof를 엉뚱한 곳에 넣어서 입력이 한개가 더 들어와서 헤맸다. 앞으로 주의해야겠다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<pair<int, int>> v;
	while (true) {
		int white, black;
		cin >> white >> black;
		if (cin.eof()) break;
		v.push_back({ white,black });
	}
	vector<vector<vector<int>>> dp(v.size(), vector<vector<int>>(16, vector<int>(16, 0)));

	dp[0][1][0] = v[0].first;
	dp[0][0][1] = v[0].second;
	
	for (int k = 1; k < v.size(); k++) {
		for (int i = 1; i <= 15; i++) {
			dp[k][i][0] = max(dp[k - 1][i][0], dp[k - 1][i - 1][0] + v[k].first);
			dp[k][0][i] = max(dp[k - 1][0][i], dp[k - 1][0][i - 1] + v[k].second);
		}
	}

	for (int k = 1; k < v.size(); k++) {
		for (int i = 1; i <= 15; i++) {
			for (int j = 1; j <= 15; j++) {
				dp[k][i][j] = max(max(dp[k - 1][i - 1][j] + v[k].first,
					dp[k - 1][i][j - 1] + v[k].second), dp[k - 1][i][j]);
			}
		}
	}
	cout << dp[v.size() - 1][15][15];
};