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

1. 문제이해

https://www.acmicpc.net/problem/4779

4779번: 칸토어 집합

칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로,

구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만드는 집합이다.

전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합을 만들 때,

N이 주어졌을 때 결과를 출력하는 것이 목표이다.

 

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

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

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

 

 

 

2. 문제풀이

 

N이 주어졌을 때, 칸토어 집합 규칙에 따른 결과를 출력하는 문제이다.

'-' 이 3^N개 있는 문자열부터 시작해, 가운데 부분을 점차 지워나가는 것이 칸토어 집합이다.

 

칸토어 집합의 규칙을 알아내 구현하는 것이 관건이다.

문제의 예제 입력 1을 통해 규칙을 자세히 알아보자.

 

---

 

< 예제입력 1>

아래와 같은 4개의 N이 차례로 주어지고, 다음과 같은 결과가 나온다.

 

 

N = 0

-

 

N = 0 이므로, 3^0 = 1. "-"이 만들어진다.

모든 선의 길이가 1일 때까지 반복된다는 규칙에 따라 "-"만 출력.

 

 

N = 1

- -

 

N = 1 이므로, 3^1 = 3. "---"이 만들어진다.

모든 선의 길이가 1일 때까지 가운데를 삭제. "- -" 만 출력.

 

 

N = 2

- -   - -

 

N = 2 이므로, 3^2 = 9. "---------"이 만들어진다.

모든 선의 길이가 1일 때까지 가운데를 삭제. "- -   - -" 만 출력.

 

 

N = 3

- -   - -         - -   - -

 

N = 3 이므로, 3^3 = 27. "---------------------------"이 만들어진다.

모든 선의 길이가 1일 때까지 가운데를 삭제. "- -   - -         - -   - -" 만 출력.

 

---

 

위 예제를 자세히 보면 무언가 규칙이 보일것이다.

그렇다! 칸토어 규칙에 따라 만든 N번째 결과는 N - 1 번째 결과 2개를 이어놓은 것과 동일하다.

단, 이어진 2개의 N - 1번째 결과의 사이에는 3^(N - 1)의 공백을 두고 말이다.

위와 같은 규칙을 발견했다면, 코드는 매우 간단해진다.

해당 규칙을 이용해 구현한 아래 코드를 보자.

 

 

 

3. 소스코드

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

void cantor(int n) {
	int size = pow(3, n - 1);

	// N = 0 인 경우 "-" 출력
	if (n == 0) {
		cout << "-";
		return;
	}

	// N번째 칸토어 집합 = N -1 번째 칸토어 집합을 2개 이은 것
	// 사이에 공백이 N - 1번째 칸토어 집합의 사이즈만큼 있어야 함
	cantor(n - 1);
	for (int i = 0; i < size; i++) {
		cout << " ";
	}
	cantor(n - 1);

}

int main() {
	int N;

	while (cin >> N) {
		cantor(N);
		cout << "\n";
	}

	return 0;
}

2. 문제풀이에서 도출한 규칙을 이용해 작성한 코드이다. 필자는 재귀함수를 이용해 구현했다.

메인함수에서 N을 입력받고, 따로 몇 개를 입력받는다거나, 입력이 끝났음을 나타내는 표시가 없으므로,

while문 안에 cin >> N 을 넣어 N을 차례로 입력받는다.

 

while문 내부에서는 단순히 cantor라는 함수를 호출하고, 호출 뒤에는 개행해준다.

cantor 함수는 이름 그대로 칸토어 집합 결과를 도출하는 함수로, N을 매개변수로 받는다.

매개변수로 받은 N을 이용해 N번째 칸토어 집합 결과를 도출한다.

2. 문제풀이에서 이야기 했듯, N번째 칸토어 집합의 결과 = (N - 1)번째 칸토어 집합의 결과 2개를 이은 것 이므로,

재귀함수를 통해 (N - 1)번째 칸토어 집합 결과를 호출한다.

단, 두개의 (N -1)번째 칸토어 집합 사이에는 3^(N - 1) 만큼의 공백이 필요하므로, for문을 통해 공백을 표현해주었다.

 

 

---

문제에 대한 질문이나 지적은 언제나 감사하게 받고 있습니다.😊