4779번 칸토어 | python

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

4779번: 칸토어 집합

 

문제
칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다.

전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자.

1. -가 3N개 있는 문자열에서 시작한다.
2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.
3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.

예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다.

---------------------------

여기서 가운데 문자열을 공백으로 바꾼다.

---------         ---------

남은 두 선의 가운데 문자열을 공백으로 바꾼다.

---   ---         ---   ---

한번 더

- -   - -         - -   - -

모든 선의 길이가 1이면 멈춘다. N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램을 작성하시오.

 

입력
입력을 여러 줄로 이루어져 있다. 각 줄에 N이 주어진다. 파일의 끝에서 입력을 멈춘다. N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.

 

출력
입력으로 주어진 N에 대해서, 해당하는 칸토어 집합의 근사를 출력한다.

---

이 문제를 보았을 때, 재귀를 이용하여 풀면 되겠다는 생각을 했고 이제 어떻게 나눠야하는가 하는 고민을 했다. 일단 3등분으로 재귀가 진행이 되어야한다는 것은 주어진 문제에서 3^N 에서 알 수 있었다.
나는 좀 번거롭게 푼 듯한 방식이지만, 3^N 만큼 리스트를 만들어서 재귀를 진행시켰다. 그다음에는 Kantoer라는 재귀를 진행시키는데 n // 3, ( 2 * n) // 3 구간으로 나누어 가운데 리스트는 공백으로 바꾸고 양 끝은 다시한번 재귀를 진행시키는 방식으로 변환한다. 해당 재귀를 진행하고 나서 중지되는 조건이 재귀로 받은 리스트의 길이가 3인 경우이다.(길이가 3일때 return을 “- -“가 됨)

import sys

input = sys.stdin.readline


def Kantoer(n, lines):
    a, b, c = lines[:n // 3], lines[n // 3: (2 * n) // 3], lines[(2 * n) // 3:]
    if n == 3:
        return f"{''.join(a)} {''.join(c)}"
    else:
        return f"{''.join(Kantoer(n // 3, a))}{' ' * (n // 3)}{''.join(Kantoer(n // 3, c))}"

while True:
    try:
        n = int(input())
        lines = ['-' for _ in range(3 ** n)]
        if not n:
            print('-')
        else:
            print(Kantoer(3 ** n, lines))
    except:
        break

문제 자체가 계속 값을 받고 해당 값에 대해 출력값을 주므로 입력이 없는 경우에는 종료하는 trigger를 설정해놓는다.