골드3 - 백준 16438 원숭이 스포츠

백준 16438 원숭이 스포츠

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

접근방법

처음에는 팀을 나누는 것을 순차적으로 생각을 해보다가 문득 반으로 나누는 생각이 들었다.
N의 최대 개수가 99개이기 때문에 2^7이면 충분히 7개의 팀으로 나누어질 수 있었고, 분할정복을 이용해서 풀었다.

풀이

organization함수에 범위를 넣고 해당 범위의 반은 'A'로, 나머지는 'B'를 입력하여 games 벡터에 저장해주었다. 그리고 나누어진 범위를 각각 organization 함수에 다시 넣어서 재귀로 대진표를 구해주었다.
마지막까지 가서 더이상 나누어질 수 없는 경우에는 전부 'B'로 입력되는데 모든 원숭이가 같은 팀이 되면 안되므로, 그 중 한마리만 A팀으로 바꿔주어 답을 출력했다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<string> games;
bool flag = false;

void organization(int layer, int start, int end)
{
	if (layer == 7)
		return;
	int mid = (start + end) / 2;

	for (int i = start; i < mid; i++)
		games[layer] += 'A';
	for (int i = mid; i < end; i++)
		games[layer] += 'B';

	organization(layer + 1, start, mid);
	organization(layer + 1, mid, end);
}

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

	int N;
	cin >> N;
	string s = "";
	string temp = "";
	for (int i = 0; i < 7; i++)
		games.push_back("");
	organization(0, 0, N);
	for (int i = 0; i < N; i++)
	{
		s += 'B';
		if (i == 0)
			temp += 'A';
		else
			temp += 'B';
	}

	for (int i = 0; i < 7; i++)
	{
		if (games[i] == s)
			cout << temp << endl;
		else
			cout << games[i] << endl;
	}
}