(4779) 칸토어 집합

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

단계별로 풀어보기

19단계(재귀) 5번째

 

 

 

3등분 한 뒤 가운데 문자열을 지우고 양쪽 문자열에 같은 과정을 반복하는 방식을 재귀로 구현하면 된다.

 

 

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  vector<char> v;
  
  auto func= [&](auto self, int l, int r) -> void {
    if(l==r)  return;
    
    int len= (r-l+1)/3;
    
    self(self, l, l+len-1);
    for(int i=l+len;i<r-len+1;i++)  v[i]= ' ';
    self(self, r-len+1, r);
  };
  
  while(cin >> n){
    int x= 1;
    for(int i=0;i<n;i++)  x*= 3;
    
    v= vector<char> (x, '-');
    
    func(func, 0, x-1);
    
    for(int i=0;i<x;i++)  cout << v[i];
    cout << "\n";
  }
  
  return 0;
}