[백준 16438번] 원숭이 스포츠

난이도: 골드 III

문제 링크: https://www.acmicpc.net/problem/16438

16438번: 원숭이 스포츠

 

백준 16438번 문제 원숭이 스포츠

문제의 설명이 조금 어려운데, 요약하면 다음과 같습니다.

N개의 원소에 대해, 총 7번의 기회 이내에 배열 내의 원소 i가 원소 j (i != j)와 다른 경우가 적어도 한 번 이상 존재해야 합니다.

 

문제의 조건을 유심히 살펴보고 분석해 보면 다음과 같은 사실을 알 수 있습니다.

N은 최대 99인데, 주어진 주는 7주입니다.

전체 원숭이를 재귀적으로 반씩 나누어 팀을 할당하는 방법을 생각해 보면, 2^7 = 128이므로 N은 7번 이내에 무조건 모든 원숭이들이 각자 다른 팀이 되도록 할 수 있습니다.

 

그러면 앞서 말한대로, 전체 원숭이를 반으로 나누고, 두 그룹을 각자 다른 팀에 할당하는 과정을 합니다.

이후, 각 그룹에 대해, 위 과정을 반복합니다. 즉, 각 그룹을 반으로 나누어 팀 A와 B에 할당합니다.

따라서 이는 재귀로 구현할 수 있습니다. 분할 정복 (divide and conquer) 방법으로 접근하는 것입니다.

 

n = 7인 경우 (문제에서 주어진 예시), 2^3 = 8이 n보다 큰 가장 작은 2의 제곱수 입니다. 따라서 위 과정을 3번 반복하면 모든 경우의 수를 얻을 수 있습니다.

하지만 문제에서는 총 7줄의 답을 출력하는 것을 요구하므로, 이에 대한 처리를 해야 합니다.

앞에서 문제의 조건은 다 갖추었으므로, 저는 남은 줄을 모든 원숭이들이 한 마리만 빼고 전부 A팀에 속하는 경우를 출력하였습니다.

 

	#include <iostream>
	#include <vector>
	#include <string>
	#include <algorithm>
	using namespace std;
	int n;
	int print_count = 0;
	char answer[8][101];
	void combination (int start, int end, int depth) {
	if (start >= end || depth == 7) return;
	print_count = max(print_count, depth);
	int mid = (start + end) / 2;
	for (int i = start; i <= end; i++) {
	if (i <= mid) answer[depth][i] = 'A';
	else answer[depth][i] = 'B';
	}
	combination(start, mid, depth+1);
	combination(mid+1, end, depth+1);
	}
	int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	combination(1, n, 0);
	for (int i = 0; i <= print_count; i++) {
	for (int j = 1; j <= n; j++) {
	if (answer[i][j] == '\0') {
	if (j % 2 == 1) answer[i][j] = 'A';
	else answer[i][j] = 'B';
	}
	cout << answer[i][j];
	}
	cout << '\n';
	}
	int b_loc = 0;
	while(print_count != 6) {
	for (int i = 0; i < n; i++) {
	if (i == b_loc) cout << 'B'; else cout << 'A';
	}
	cout << '\n';
	b_loc = (b_loc+1) % n; print_count++;
	}
	return 0;
	}

view raw 16438_원숭이스포츠.cpp hosted with ❤ by GitHub

배열의 빈 곳이 있는 경우 확인하고 홀수인 경우 A, 짝수인 경우 B를 넣고 출력해 주었습니다.

 

채점 결과

예외 처리 (N < 7인 경우), 버그 잡기 등 때문에 몇 번 틀리고 나서 맞았네요.