[백준알고리즘] 4779번: 칸토어 집합-C++

 

4779번: 칸토어 집합 (acmicpc.net)

4779번: 칸토어 집합

칸토어 집합이 뭔지 궁금해서 찾아봤다.

칸토어 집합 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

 

근데 내용이 뭔 말인지 모르겠어서 일단 풀었다. 문제 자체는 문자열을 이용해 쉽게 풀 수 있었다. 같은 구조가 내부적으로 반복되기 때문에 분할 정복 알고리즘을 이용했다.

---

문제 풀이

선의 길이가 1이 될 때까지 반복하면서, 선을 계속해서 3등분을 했다. 첫 번째 조각과 마지막 세 번째 조각은 재귀적으로 칸토나 집합을 적용했다. 두 번째 조각은 선을 없애고 빈 문자(space)로 교체했다.

 

문자열과 재귀를 이용해 쉽게 문제를 풀 수 있었다.

#include <cstdio>
#include <cmath>
#include <string>

std::string applyCantor(const std::string &sSet);

int main(void) {
	int iExponent = 0;
	while ( EOF != ::scanf("%d", &iExponent) ) {
		std::string sOriginal((size_t) ::pow(3, iExponent), '-');
		std::string sCantor = applyCantor(sOriginal);
		printf("%s\n", sCantor.c_str());
	}
	return 0;
}

std::string applyCantor(const std::string &sSet) {
	const size_t siLen = sSet.size();
	if ( 1 == siLen ) {
		return sSet;
	}
	const size_t sSubLen = (size_t) siLen / 3;
	const std::string sSubCantor = applyCantor(sSet.substr(0, sSubLen));

	std::string sRet;
	sRet.append(sSubCantor);
	sRet.append(std::string(sSubLen, ' '));
	sRet.append(sSubCantor);

	return sRet;
}