[백준 4779] 칸토어 집합 (python)

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

4779번: 칸토어 집합

칸토어 집합 문제

(3 ** 입력값)의 개수만큼 -로 이루어진 직선을 조건에 맞게 3 등분해 나가면서 자르는 문제

분할 정복을 활용하여 해결할 수 있었다.

📌문제 접근 포인트

※그림으로 보는 진행 과정

1. 3등분으로 분할

2. 분할한 가운데 지우기

3. 각각의 선 다시 3 분할하기

4. 각 선 다시 지우기 

5. 위 과정을 반복

 

1. 위 그림과 같은 과정으로 진행해 간다. 이걸 구현해 보자.
2. 반복해서 자를 수 있을 때까지 잘라줘야 하니, 재귀를 이용하여 탐색하자
3. 가운데 문자들을 공백으로 만들어야 하니 가운데를 찾아줄 방법을 생각해 보자.
시작점을 기준으로 시작점+n//3부터 시작점+(n//3)*2까지 사이를 지워주면 된다.
예를 들어보자
N = 1이면 n = 3이니까  3/3 = 1부터 (3/3)*2까지 사이를 지운 - -가 답이 될 것이다.
N = 2이면 n = 9가 되니까 9/3 = 3부터 (9/3)*2까지 사이를 지운 ---   ---가 먼저 생성될 거고,
다음 진행을 반복하면 3/3 = 1부터 (3/3)*2까지 사이를 지우고, 오른쪽 선의 시작지점이 6이므로 6+1부터 6+2까지 사이를 지워서 - -   - -가 된다.
즉 자를 때 왼쪽으로 갈경우 시작점 0부터 자를 수 있을 것이고, 오른쪽은 시작점 (n//3)*2부터 자르기 시작한다.
4. 파일의 끝에서 입력을 멈추므로 while문과 try except 구문을 이용하여 EOF에러 발생 시 끝나게 설정해 주면 해결 완료!

반응형

⚙ 내가 푼 정답코드

def cut(a,n): # a = 시작점
    if n == 1:
        return
    for i in range(a + n//3, a +(n//3)*2): # 가운데 문자열을 공백으로
        result[i] = ' '
    cut(a, n//3) # 왼쪽 잘라나가기
    cut(a + n//3 * 2, n//3) # 오른족 잘라나가기
import sys
while True:
    try :
        N = int(sys.stdin.readline())
        result = ['-']*(3**N) # 최초 리스트 집합
        cut(0,3**N) # 자르기
        print(''.join(result))
    except : # EOF 발생시
        break # 종료