[백준 4779] 칸토어 집합

문제 출처 : https://www.acmicpc.net/problem/4779

 

이 문제는 재귀함수나 분할정복으로 구현할 수 있는 문제 입니다. 다빈치코딩 알고리즘 재귀 부분에 이 문제가 없어 아무 생각없이 작성했는데 분할 정복에서 이미 작성해 놓았다는 것을 알았습니다. 분할정복과 재귀 두 방법을 비교해 보면서 확인해 보시기 바랍니다.

 

분할 정복으로 푼 방법 : https://wikidocs.net/206410

02. 칸토어 집합[백준 4779]

 

칸토어 집합이란 0과 1 사이를 삼등분 해나가면서 가운데 부분을 지워나가는 집합 입니다. 가운데를 지워나가면 아래와 같은 형태가 됩니다.

규칙적인 형태이기 때문에 재귀로 생각하기 좋은 문제 입니다. 앞 선 문제들과의 차이점은 앞에서는 재귀 함수가 한 번만 사용되었지만 여기서는 양쪽에 똑같은 형태로 재귀함수를 사용해야 한다는 것입니다. 하나의 재귀함수 안에 여러개의 재귀 함수가 들어가야 하는 것입니다.

코드 작성

그럼 코드를 작성해 보겠습니다.

종료 조건 구현

0이 입력 되었을 때 “-” 하나만 출력됩니다. 따라서 재귀 함수 recur(0)은 “-” 만 출력하면 됩니다.

def recur(n):
    if n == 0:
        return "-"

print(recur(0))

0이 입력되면 “-”를 출력하는 것이 이 문제인 칸토어 집합 재귀함수의 종료조건 입니다.

재귀 함수 구현

이제 recur(1)을 생각해 보겠습니다. 재귀 함수 모양을 생각해보면 아래와 같은 형태로 만들 수 있습니다.

recur(1) = recur(0) + 빈 칸 + recur(0)

마찬가지로 recur(2)는 다음과 같은 형태가 됩니다.

recur(2) = recur(1) + 빈 칸 + recur(1)

재귀 함수의 모형이 갖추어졌기 때문에 빈 칸의 개수만 맞게 한다면 쉽게 구현이 됩니다.

빈 칸의 개수

예제 문제를 확인해 보면 n이 3일 때는 빈 칸이 9개이고, n 이 2일 때는 빈 칸이 3개 입니다. 즉 빈 칸의 개수는 3 ** (n - 1)개가 됩니다. 재귀 함수 모형도 만들어졌고, 빈 칸의 개수도 알기 때문에 이제 함수를 구현하면 됩니다.

def recur(n):
    if n == 0:
        return "-"
        
    nn = n - 1
    side = recur(nn)
    center = " " * (3 ** nn)
    
    return side + center + side

양 옆을 재귀 함수로 구현하여 결과를 받아오고 가운데는 빈 칸으로 처리하였습니다. 왼쪽, 오른쪽 모양이 다르다면 재귀 함수를 각각 사용하였겠지만 이 문제에서는 같은 모양이기 때문에 하나의 재귀 함수를 사용하여 양쪽에 붙여주는 형태로 만들었습니다. return 받은 결과를 더해주어 출력해주면 칸토어 집합을 구현할 수있습니다.

입력 받기

재귀 함수를 구현하였으니 이제 입력 받는 부분을 만들어 보겠습니다. 이 문제에서는 입력이 몇 개인지 주어지지 않았습니다. 즉 입력이 없을 때까지 반복해야 합니다. 보통 이런 경우는 try except문을 사용하여 문제를 해결합니다.

try except 문을 모른다면 아래 링크를 통해 예외처리에 대해 확인해 보시기 바랍니다.

https://wikidocs.net/192474

18. 예외처리

 

while True:
    try:
        n = int(input())
        print(recur(n))
    except:
        break

전체 코드

전체 코드를 확인해 보겠습니다.

def recur(n):
    if n == 0:
        return "-"
    nn = n - 1
    side = recur(nn)
    center = " " * (3 ** nn)
    return side + center + side

while True:
    try:
        n = int(input())
        print(recur(n))
    except:
        break