백준 4779번: 칸토어 집합 (C++)

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

4779번: 칸토어 집합

---

Solved By: Divide & Conquer

 

이러한 출력 문제는 (별 찍기와 비슷함) 어떻게 작동해야 할지는 알겠으나 코드로 짜기는 어렵습니다.

다음 Recursive Call에서 어떤 Parameter로 넘겨주어야 하는지가 제일 까다롭습니다.

 

항상 별찍기 문제들에서나 실수하던 부분을 이번 문제에서도 실수했었습니다.

Divide & Conquer

Parameter 실수에 대한 해결법은 항상 머리가 아닌 몇 개의 TC만 노트로 써봐도 풀린다.

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

int n;
string s;

void dq(int N, int st, int en){
    if(N == 1) return;
    int n3 = N / 3;
    for(int i = st; i < en; i++){
        if(i >= st + n3 && i < st + 2 * n3) s[i] = ' ';
    }
    
    // key point
    dq(n3, st, st + n3);
    dq(n3, st + 2 * n3, st + 3 * n3);
}

int main(){
    while(cin >> n){
        s = "";
        for(int i = 0; i < pow(3, n); i++){
            s += '-';
        }
        dq(pow(3, n), 0, pow(3, n));
        cout << s << '\n';
    }
    return 0;
}