[백준-파이썬] 4779: 칸토어 집합

문제로 가기

길이가 3^N인 리스트를 만들었다. 칸토어 집합은 일단 -가 3^N개인 문자열에서 시작하니까~~
그 후에 sol함수를 실행한다. 재귀함수인데, 몇 번 더 볼지, 시작점과 끝점을 받는다.
시작점과 끝점은 그 선 중에서 어느 부분을 보고 있는지를 뜻한다.
몇 번 더 볼지가 0이 되면, return한다.
그게 아니라면 시작점과 끝점을 가지고 3등분을 해서, 가운데 부분은 공백으로 바꾼다.
왼쪽과 오른쪽 부분은 또 sol 함수로 넣는다. 몇 번 더 볼지는 1 감소하고, 왼쪽과 오른쪽 부분의 시작점과 끝점을 구해서 그걸 넣는다.

import sys

input = sys.stdin.readline


def sol(n, i, j):  # 몇 번 더 볼지, 시작점, 끝점
    if n == 0:
        return

    # 3등분
    cnt = (j - i + 1) // 3  # 각각 몇 개씩인지
    # 왼쪽
    sol(n - 1, i, i + cnt - 1)
    # 가운데 -> 공백으로 바꾸기
    for k in range(i + cnt, i + cnt * 2):
        answer[k] = ' '
    # 오른쪽
    sol(n - 1, i + cnt * 2, i + cnt * 3 - 1)


while True:
    try:
        n = int(input())
        answer = ['-'] * (3 ** n)
        sol(n, 0, 3 ** n - 1)
        print(''.join(answer))
    except:
        break