https://www.acmicpc.net/problem/4779
시간 1초, 메모리 128MB

input :

• N (0 ≤ N ≤ 12)

output :

• 칸토어 집합의 근사를 출력

조건 :

1. -가 3N개 있는 문자열에서 시작한다.

2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.

3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.

---

1년 전의 나를 반성하는 문제이다. 과거에도 다 풀어놓고는 출력 이상하게 해서 틀렸다.;;

재귀를 했을 때 트리로 표현한다면 12레벨 정도로 작기 떄문에 충분히 가능하다는 걸 알 수 있다.

다음 풀이

1. "-"를 다 채운 배열의 구간, 배열을 넘겨서 수행
2. 3등분?

"-"를 모두 채운 후에 배열을 넘겨서 하는 것이 편할 수 있다. 병합정렬을 수행하듯이 말이다.
Recursive 케이스로 3등분을 나눠서 좌, 우의 배열은 재귀를 수행하고 중간은 내버려 둔다.
Base 케이스는 문제에서 나오듯이 길이가 1일 때 재귀를 완료한다.

배열을 출력할 때, 문자열이기 때문에 join을 사용하는 것이 편하고 제곱을 사용하기 편하도록 "**"을 사용한다.

import sys
sys.setrecursionlimit(100000)

def Cantor(three_list):
    if len(three_list) <= 1:
        return three_list

    branch = len(three_list) // 3
    fir_section = Cantor(three_list[:branch])
    sec_section = ' ' * branch
    thr_section = Cantor(three_list[branch * 2:])

    return fir_section + sec_section + thr_section

while True:
    try:
        N = 3 ** int(input())
        threes = '-' * N

        hypen = Cantor(threes)
        print("".join(hypen))
        
    except EOFError:
        break