4779 칸토어 집합

www.acmicpc.net/problem/4779

4779번: 칸토어 집합

 

딱 실버 분할정복 문제.

 

'-'만 \( 3^{N} \)개 있는 문자열을 3등분으로 나누어 가운데 부분은 공백(space)로 바꾸고 왼쪽, 오른쪽은 다시 같은 작업을 반복하는 문제.

 

 

다음 그림과 같이 (부분)문자열의 첫번째 인덱스를 start로 하고, 3등분한 문자열의 오른쪽 부분의 첫번째 인덱스를 end 라고 하자.

size를 3등분된 문자열의 크기라고 할 때, end = start+size+size 라고 할 수 있다.

 

이 때, (부분)문자열의 인덱스 start+size 부터 end-1 까지 공백으로 바꾸어준다.

그리고 재귀적으로 오른쪽 부분, 왼쪽 부분을 각각 3등분하여 같은 작업을 반복한다.

이 작업을 3등분 할 수 없을 때까지 (1칸만 남을 때까지) 해주면 된다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
void divide_conquer(string& k, int size, int start)
{
    if(size == 1) return;
    size /= 3;
    int end = start+size+size;
    for(int i=start+size;i<end;i++)
        k[i] = ' ';
    divide_conquer(k, size, start);
    divide_conquer(k, size, end);
}
 
int main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    while(scanf("%d", &n) == 1)
    {
        string k = string((int)pow(3, n), '-');
        divide_conquer(k, k.size(), 0);
        cout << k << endl;
    }
    return 0;
}