[C++] 백준 4779. 칸토어 집합

문제

입출력

풀이

재귀 문제에는 약간의 ptsd가 있는데
(이유는 모르겠지만 너무 무섭고 어렵게 느껴진다 ㅠ)
비록 51분이 걸렸지만 이 문제를 스스로 풀어내며 8.3% 정도 극복이 됐다.

뭔가 문자열 자체로 가지고 풀기에 좀 코드가 지저분해질 것 같기도 하고
메모리 측면에서 string이나 char보단 bool이 나을 것 같아
vector<bool> v(N, true)를 가지고 시작했다.

이 문제를 풀기 전에,
어제 어렵게 이해한 합병 정렬 코드를 복습했는데
합병 정렬 알고리즘 원리와 매우 유사한 문제인 것 같다고 느꼈다.

반갈(2등분) + 머지의 반복인 합병 정렬과 다른 점은
3등분을 한다는 것, 머지 과정이 필요없다는 것이다.

뚫을 범위 계산 + 가운데 뚫기를 반복할건데
범위값이 1이면(지 혼자 있을 때) return하고
그렇지 않으면 뚫란 부위의 좌우 각각을 다시 함수로 넘긴다.

테스트케이스 수가 미정일 때

입력의 개수가 주어지지 않을 땐,
아래 두 가지 방법을 활용하자.

방법 1

int n;
while (1) {
	cin >> n;
    if (cin.eof() == 1) break;
	solution();
}

방법 2

int n;
while (cin >> n) {
	solution();
}

코드

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

void solution(vector<bool>& v, int l, int r) {
	if (l == r) return;
	int st = l + (r - l + 1) / 3;
	int en = st + (r - l + 1) / 3;
	for (int i = st; i < en; i++) v[i] = false;
	solution(v, l, st - 1);
	solution(v, en, r);
}

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) cout << "-";
		else {
			int size = pow(3, n);
			vector<bool> v(size, true);
			solution(v, 0, size - 1);
			for (int i = 0; i < size; i++) {
				if (v[i]) cout << "-";
				else cout << " ";
			}
		}
		cout << "\n";
	}

	return 0;
}

채점