백준 4779 칸토어 집합 / C++

문제 : 4779

풀이 point

재귀를 통해 분할해서 선들을 지워나간다.
1/3, 2/3, 3/3 중 2/3에 해당하는 선들을 지운다.
이것을 선의 길이가 1일 될 때까지 반복한다.(n==0이 될 때까지)

1/3값은 (end-start+1) / 3 형태로 구할 수 있다.
(start+end)/3은 절대적인 값이므로 값이 변동될 수 있기 때문에 좋지 않다.

이런 문제를 풀 때는 비율로 접근하는 것이 좋다.

풀이 방법

1. 선을 지우는 방법
2. 패턴을 찾아 선을 출력하는 방법(별 찍기와 유사)

0~1/3은 다시 재귀, 1/3~2/3은 지우기, 2/3~3/3은 다시 재귀

코드

//백준 4479, 칸토어 집합
#include <iostream>
#include <cmath>

int n;
char line[560000];

void solve(int n, int start, int end){
    if(n == 0) return;
    int len = (end-start+1) / 3; //1/3값
    for(int i{start + len}; i<start+2*len; ++i) line[i] = ' '; //1/3부터 2/3값을 지우기
    solve(n-1, start, start+len-1); //0부터 1/3
    solve(n-1, start+2*len, end); //2/3부터 3/3까지
}

int main(){
    while(std::cin >> n){
        int size = pow(3, n);
        for(int i{0}; i<size; ++i) line[i] = '-';
        solve(n, 0, size-1);
        for(int i{0}; i<size; ++i) std::cout << line[i];
        std::cout << '\n';
    }

    

    return 0;
}