백준 4779번 칸토어 집합(c++)

4779번: 칸토어 집합

문제 분석

칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 각 구간을 3등분으로 하여 가운데 구간을 반복적으로 제외하는 방식이다. 이를 토대로 칸토어 집합의 근사를 만들고자 하는 문제이다.

문제는 3등분으로 나눈 구간을 각 1, 2, 3이라 할 때,

1. 2의 구간을 공백으로 둔다.

2. 후에 1, 3 구간을 다시 각 3등분으로 나누며 위 과정을 반복한다.

= 재귀를 사용함.

3. 모든 선의 길이가 1이면 멈춘다. = 선이 이어진 상태는 존재하지 않는다.

---

문제 풀이

1번 풀이

많은 풀이 해설에서 보여주는 일반적인 풀이이다. 즉, 칸토어 집합의 규칙을 파악하는 것이 가장 중요하다. 

문제에서 가장 핵심은, 3^N의 문자열에서, 3등분하였을 때의 가운데 부분을 지우는 것이 핵심이다.

재미있는 부분이, N의 3등분 중 하나의 길이는 N-1번째 칸토어 집합의 길이와 같다는 것을 알 수 있다. 

이를 활용하여, N-1번째 칸토어 집합의 2개는 3등분의 양 쪽에 위치하고, 남은 가운데 부분은 공백으로 채운다면 위 문제를 해결할 수 있다.

c++ 풀이1

#include <iostream>
#include <cmath>

using namespace std;

void cantor(int num){
    if(num == 0){
        cout << '-';
        return;
    } // N이 0일 경우. base case.
    
    cantor(num - 1);
    for(int i = 0; i < pow(3, num - 1); i++)
        cout << ' '; 
    cantor(num - 1); 
    // N번째 칸토어 = N-1번째 칸토어 집합('-') 2개, N-1번째 칸토어 집합(' ') 1개
}

int main (){
    int n;
    while (cin >> n){
        cantor(n);
        cout << '\n';
    }
    
    return 0;
}

2번 풀이

이는 직접 해결한 방식이다. 0일 경우, '-'를 출력시키도록 하고, 남은 부분은 공백을 채워넣는 형식이다.(규칙을 활용한 풀이) 하지만 필자는 직접 배열을 하나의 선 형태로 만들어 놓고, 삭제해야하는 부분을 공백으로 채워넣어 제거하는 형식으로 진행하였다. 이는 규칙을 활용하기보다 3등분의 가운데 부분을 삭제하도록 하는 과정을 사용했다.

아래 코드에서의 함수 파라미터 x와 y는 각각 3등분 하기 전의 칸토어 집합의 전체 길이를 가르킨다. (x는 처음, y는 끝)
즉 x + n ~ y - n은 3등분 중 가운데 범위에 공백을 채워넣는 형식을 보여준다. 

c++ 풀이2

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void Cantoa(vector<char> &vec, int x, int y, int point) {
	int n = pow(3, point) / 3;
	for (int i = x + n; i < y - n; i++) {
		vec[i] = ' ';
	}
	point--;
	if (point== 0) // base case
		return;
	Cantoa(vec, x, x + n, point); // N-1번째 칸토어 집합 사이즈
	Cantoa(vec, y - n, y, point); // N-1번째 칸토어 집합 사이즈
}

int main() {
	int N;

	while (cin >> N) {
		int cantoa = pow(3, N);
		vector<char> vec(cantoa, '-');
		if (N == 0) {
			cout << '-' << '\n';
			continue;
		} // N이 0일 경우, 조건문 수행 후 반복문 처음으로.
        
		Cantoa(vec, 0, kantoa, N);
        
		for (int i = 0; i < vec.size(); i++) {
			cout << vec[i];
		}
		cout << '\n';
	}

	return 0;
}

코드 리뷰는 언제나 환영입니다!