[백준 4779] 칸토어 집합

문제 링크 => 4779번: 칸토어 집합 (acmicpc.net)

4779번: 칸토어 집합

---

분할정복 문제이다.

 

가운데 부분을 3^(N-1) 만큼 빈칸을 출력하게 하고 양 옆을 f(n-1) 을 재귀적으로 호출하도록 하면 정답이다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

void f(int n) {
	if (n == 0) {
		cout << "-";
		return;
	}
	f(n - 1);
	for (int i = 0; i < pow(3,n-1); i++) cout << " ";
	f(n - 1);
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n;
	while ((scanf("%d", &n)) != EOF) {
		f(n);
		cout << endl;
	}

	return 0;
}