[백준/c++] 16438번 - 원숭이 스포츠

[ 문제 ]

 

 

[ 구현 ]

 

분할정복 + 해 구성하기 느낌으로 풀었다

 

핵심 아이디어는

주어진 n을 2등분해 나가면서 절반은 A로 나머지 절반은 B로 바꿔주는 것이다.

이러한 분할정복 방식을 통한다면 2^7은 128이므로 n<=99의 조건을 충분히 커버할 수 있게 된다.

(이를 위해 배열도 2차원으로 두어 몇번째 대진표에 해당하는 것인지 따로 저장해줄 필요가 있음)

 

조금 예외적인 상황으로

항상 7개의 대진표를 출력해야하며, 각 팀에 원숭이가 최소 1마리는 있어야 하는 조건을 만족해야 하므로

추가적인 처리가 필요하다.

 

 

 

[ 코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int print_cnt = 0;
char arr[8][100];


void dq(int st, int ed, int depth) {
	print_cnt = max(print_cnt, depth);

	if (st >= ed || depth == 7) return;
	
	int mid = (st + ed) / 2;
	
	for (int i = st; i <= ed; i++) {
		if (i <= mid) arr[depth][i] = 'A';
		else arr[depth][i] = 'B';
	}

	dq(st, mid, depth+1);
	dq(mid+1, ed, depth+1);
}





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

	cin >> n;

	dq(0, n - 1, 0);

	for (int i = 0; i < print_cnt; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == '\0') {
				arr[i][j] = 'A';
			}
		cout << arr[i][j];
		}
		cout << '\n';
	}

	while (print_cnt < 7) {
		cout << 'A';

		for (int i = 1; i < n; i++) {
			cout << 'B';
		}

		cout << '\n';

		print_cnt++;
	}
	return 0;
}

 

 

 

[ 마무리 및 느낀 점 ]

 

아이디어는 비교적 단순하지만 구현의 세부적인 처리에서 어려움을 느꼈다.

주기적으로 조금씩 문제를 풀어주면서 감을 잃지 말아야겠다.