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

- 문제

칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다.

전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자.

1. -가 3N개 있는 문자열에서 시작한다.

2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.

3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.

예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다.

---------------------------

여기서 가운데 문자열을 공백으로 바꾼다.

---------         ---------

남은 두 선의 가운데 문자열을 공백으로 바꾼다.

---   ---         ---   ---

한번 더

- -   - -         - -   - -

모든 선의 길이가 1이면 멈춘다. N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램을 작성하시오.

- 입력

입력을 여러 줄로 이루어져 있다. 각 줄에 N이 주어진다. 파일의 끝에서 입력을 멈춘다. N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.

- 출력

 

입력으로 주어진 N에 대해서, 해당하는 칸토어 집합의 근사를 출력한다.

- 예제

//INPUT//
//OUTPUT// 순으로 나옴.
0
-
1
- -
3
- -   - -         - -   - -
2
- -   - -

 

 

 

---

- 구상

입력 예시에 따르면, 입력되는 N은 계속해서 들어온다.

 

➡ 두 가지 방법을 찾았다.

//Solution1//
while(1){
	
    cin >> sth;
    if(cin.eof()){
    	break;
    }
}

//Solution2//
while(cin >> sth){

}

compile상으로도, 실행 과정 상으로도, Visual Studio Community 2019 환경에서는 문제가 없었다. 하지만 백준에 제출하는 곳에서는 두 번째 방법만 error가 발생하지 않았다. 그래서 이번 코드에서는 두 번째 방법을 통해 구현하자.

 

➡ 다음으로 칸토어 집합의 설명에 따라, 중간이 사라지고, 양쪽으로 찢어지는 것을 반복하는 재귀함수를 구현해보자.

 

➡ 메인 함수에서는 N을 입력받고, 3^N 길이의 string을 구현한다. 이후 재귀함수에 pass by reference로 넘겨, 함수 실행 내용이 string에 영향이 가도록 한다.

 

➡ 함수에 넣었을 때, 삭제시키는 부분의 위치가 각 함수마다 다르다. 삭제를 시작하는 점의 정보를 함수에 넣지 않는다면, Cantor Set에 근사하는 형태를 만들 수 없을 것이다.

 

➡ 또한 현재 함수를 통해 삭제해야되는 길이를 알려면, 원래 어느정도 길이였는지를 알아야한다.

 

➡ 그래서 함수의 instance에는 string, 시작점(int), 길이(int)가 들어올 것이다.

 

➡ 삭제 범위는 시작 점으로부터 항상 길이/3~2*(길이/3)의 위치에 있을 것이다.

 

 

 

---

- 구현

//1//
for (int i = 0; i < cnt; i++) {
	Cantor += "-";
}

//2//
Cantor.assign(cnt,'-');

위 둘의 차이가 나는 이유는 초기화 측면에 있다. while문 밖에서 Cantor를 초기화 시켜주게 된다면, 1번인 for문의 경우, 길이가 이전의 값들이 사라지지 않고, 계속 이어 붙여진다. 그래서 1번을 사용시, while문 안에서 string Cantor="";로 선언해야한다.

 

assign(a,b)라는 함수는 b라는 문자로 채워진 길이가 a인 문자열을 만드는 식으로, 이것 하나만으로 while문 내에서 초기화와 길이설정이 가능해진다.

그래서 assign()함수를 사용할 것이다,

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

void CantorElim(string& sec, int start, int length) {
	if (length == 0) {
		return;
	}

	int length_semi = length / 3;
	int mid = start + length_semi;

	for (int i = mid; i < mid + length_semi; i++) {
		sec[i] = ' ';
	}

	CantorElim(sec, start, length_semi);
	CantorElim(sec, mid + length_semi, length_semi);
}

int main() {

	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int cnt, cnt_sup;
	string Cantor;

	while (cin >> cnt_sup) {

		cnt = pow(3, cnt_sup);
		Cantor.assign(cnt, '-');
		CantorElim(Cantor, 0, cnt);
		cout << Cantor << endl;

	}


	return 0;
}