[python] 백준 4779번 - 칸토어 집합

 

모든 선의 길이가 1이 될 때까지 선을 3등분 한 후, 가운데를 공백으로 바꾸는 문제.

재귀로 분류되어 있는 문제이다.

 

가장 먼저 규칙을 찾아 보았다.

 

N == 0일 때

"-"

 

N == 1 일 때

"- -"

 

N == 2일 때

"- -   - -"

 

N == 3일 때

"- -   - -         - -   - -"

칸토어 집합의 규칙에 따라서 선을 그리게 되면

N번째 선은 N - 1번째 선을 2개 이어 놓았다는 것을 알 수 있다.

그리고 두 선의 사이에는 3^(N-1)의 공백이 생기는 규칙이 있다.

그래서 위의 규칙을 구현하는 코드를 다음과 같이 작성하였다.

def fn(n):
    if n == 0:
        return '-'
    else:
        prev_line = fn(n - 1)
        space = ' ' * (3 ** (n - 1))
        return prev_line + space + prev_line

while True:
    try:
        N = int(input()) # 3^N
        print(fn(N))
    except:
        break

N = 0일 때는 단순히 길이가 1인 선을 반환한다.

그것이 아니라면 "N-1번째 선, 3^(N-1)칸의 공백, N-1번째 선" 형태의 선을 반환하게 된다.

이전의 선을 fn(n-1)의 반환값을 재귀적으로 가져오는 형태.