[백준OJ] 4779번 칸토어 집합

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

4779번: 칸토어 집합

---

 

풀이

전체문제를 부분적으로 쪼개어 문제를 해결하는 분할정복에 해당하는 문제이다.

 

1. 입력받은 N값으로 초기 문자열을 만들어 준다.

2. 재귀함수를 이용하여 분할정복을 시작한다.

2-0. 베이스케이스 = 해당 토막의 길이가 1

2-1. 3등분을 한다.

2-2. 첫번째 토막은 재귀함수를 호출한다.

2-3. 두번째 토막은 모두 공백으로 바꾸어준다.

2-4. 세번째 토막은 재귀함수를 호출한다.

 

코드

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

string init(int n) {
	string str = "";
	for (int i = 0; i < n; i++) str += "-";
	return str;
}

void make_blank(string& str, int st, int end) {
	for (int i = st; i <= end; i++) {
		str[i] = ' ';
	}
}

void func(string& str,int st,int end) {
	if (st==end) {
		return;
	}
	int size = (end-st+1) / 3;

	func(str, st, st+size - 1);
	make_blank(str, st+size,end-size);
	func(str, end - size + 1, end);

}

int main() {
	int n;
	while (cin >> n) {
		n = pow(3, n);
		string str = init(n);
		func(str, 0, n - 1);
		cout << str << "\n";
	}
	return 0;
}