C++ 알고리즘 - 백준 4779 칸토어 집합

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

/******** 전역변수 ********/
vector<int> kan(550000);

/******** 함    수 ********/
void kantoa(int n, int m){  // n: 문자 자를 인덱스 위치, m: 자를 개수
    // 자를 개수가 없다면 리턴
    if (m == 0) return;

    // n의 위치부터 m까지 공백 처리
    for(int i = n; i < n + m; i++){
        kan[i] = 0;
    }

    //재귀함수 호출 (앞으로 탐색)
    //ex: 9, 9 => 3, 3 => 1, 1
    kantoa(n - (m / 3) - (m / 3), m / 3);

    //재귀함수 호출 (뒤로 탐색)
    //ex: 9, 9 => 21, 3 => 25, 1
    kantoa(n + m + (m / 3), m / 3);
}

int main(void) {
	/******** C++ INIT ********/
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	/******** 지역변수 ********/
	int input;

	/******** 구    현 ********/
	while(cin >> input){ // EOF 일때까지 입력 받음
        kan.clear();

        // 0일때는 -
        if(input == 0){
            cout<< "-" <<endl;
            continue;
        }

        // 입력값을 3제곱 하여 저장
        input = pow(3, input);

        // 입력된 값의 3제곱 만큼 벡터에 1 저장
        for(int i = 0; i < input; i++){
            kan[i] = 1;
        }

        // 3으로 나눈 후 칸토어 집합 함수 호출 (공백으로 바꿀 부분 검색)
        kantoa(input / 3, input / 3); 

        // 1이면 -, 0이면 ' ' 출력
        for(int i = 0; i < input; i++){
            if(kan[i] == 1) cout << "-";
            else cout << " ";
        }

        cout << endl;
    }
}

 

훨씬 더 간단하게 할 수 있는 방법은 많다.