[백준/BOJ] 4779번 칸토어 집합 (C/C++)

백준 온라인 저지(BOJ) 4779번 칸토어 집합

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

4779번: 칸토어 집합

* 사용언어 : C언어, C++

 

1. 문제

'-'가 3^N개 있는 문자열을 3등분 한 뒤 가운데 문자열을 공백으로 변경

공백 양 옆의 두 선을 3등분하고 공백으로 바꾸는 작업을 선의 길이가 1이 될 때 까지 반복

주어진 N에 대해 위 과정의 결과값을 출력

 

2. 풀이

재귀를 통해 절차를 반복하여 푸는 것이 핵심이지만

여러 개의 Test Case에서 동일한 절차를 반복하는 것은 적합하지 않은 것 같다고 보았습니다.

 

그래서 N의 최대값(12)에 따라 문자열을 3^12 크기로 선언하고,

N이 12일 때의 결과값을 재귀 함수를 활용하여 미리 처리하여 저장해두었습니다.

 

이후 N이 주어질 때마다 해당 되는 길이만큼만 출력하게 했습니다.

풀이 자체는 단순하니 아래 코드로 설명 대체하겠습니다.

 

매우 쉬운 문제라고 생각했었지만

저는 cantor 함수 내 index(s, e, m1, m2)를 처리하는 과정에서 실수가 많이 있었습니다.

배열의 index, 그리고 debug 모드에 익숙해질 필요가 있는 것 같습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
4779_칸토어 집합
2160KB	0ms
*/
#include <cstdio>

const int CLM = 531441; // 3^12
char str[CLM];
int cnts[13], N;

void cantor(int s, int e) {
	if (s + 1 >= e) return;

	int dist = (e - s + 1) / 3;
	int m1 = s + dist;
	int m2 = m1 + dist;

	for (int i = m1; i < m2; ++i) str[i] = ' ';
	cantor(s, m1);
	cantor(m2, e);
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	for (int i = 0; i < CLM; ++i) str[i] = '-';
	cantor(0, CLM - 1);

	int cnt = 1;
	for (int i = 0; i < 13; ++i) {
		cnts[i] = cnt;
		cnt *= 3;
	}

	while (scanf("%d", &N) == 1)
		printf("%.*s\n", cnts[N], str);
	
	return 0;
}

* printf("%.*s", 길이, 문자열)로 문자열을 원하는 길이만큼만 출력할 수 있습니다.