[n4779] 칸토어 집합 in python

 

pc.net/problem/4779

4779번: 칸토어 집합

---

(처음 든 생각)

3등분씩 진행하면,

N을 3으로 나눈 값만큼 계속 쪼개지는구나...

뭔가 트리 모양처럼 쪼개지네?

 

반씩 나눠지는 걸 보니.. 재귀함수를 써야하나..?

-의 개수가 1개 남을경우까지만 탐색을 해야하니까

재귀함수를 한 번 써봐야겠다

 

배열을 쓸까 아니면 문자열로 쓸까 고민하다가

그냥 배열 씀.. (문자열 하다가 무슨 이유 때문인지 모르겠지만 그만둠)

 

---

(처음 풀이)

입력값을 얼마나 넣는 지 알 수 없기 때문에

try: except: 문으로 작성해야했다.

입력 도중 파일의 끝에 도달하면 반복문을 종료하도록 EOFError를 썼다.

(이거 처리 안해주면 EOFError 오류남)

 

recursive 안에 있는 for문 범위때문에 

애를 많이 먹었다.

 

일단 recursive 함수의 인자로는 array, start, now_length가 있다.

맨 처음에는 recursive(array,0,pow(3,n))을 해준다.

즉 recursive(array,0,27) ==> n==3

 

 

이 코드의 재귀함수 과정을 표현하면 아래와 같다. 

 

 

현재 3등분한 각각의 너비를 temp라는 변수에 저장

temp=27이면 아직 3등분을 하지 않은 초기상태

temp=9이면, 현재 array,0,9와 array,18,9가 실행된 상태

 

 

 

왼쪽 트리의 재귀함수는 recursive(array,start,temp)

오른쪽 트리의 재귀함수는 recursive(array,start+temp*2,temp)

 

temp=9일때, 왼쪽 트리의 start와 오른쪽 트리의 start 차이는 temp*2 = 18

temp=3일때, 왼쪽 트리의 start와 오른쪽 트리의 start 차이는 temp*2 = 6

temp=1일때, 왼쪽 트리의 start와 오른쪽 트리의 start 차이는 temp*2=2

이를 이용하여 재귀함수 구현

def recursive(array, start, now_length):
    temp = now_length // 3

    if temp == 0:
        return

    for i in range(start + temp, start + temp * 2):
        array[i] = ' '

    recursive(array, start, temp)
    recursive(array, start + temp * 2, temp)


while True:
    try:
        n = input()
        if n == '':
            break
        else:
            n = int(n)
            array = ['-' for i in range(pow(3, n))]
            recursive(array, 0, pow(3, n))
            answer = ''
            for i in array:
                answer += i
            print(answer)

    except EOFError:
        break

# 입력 도중에 파일의 끝을 만나면 반복문 종료

 

 

---

(인터넷 참고 풀이)

재귀함수를 풀지 않더라도 규칙을 찾아내면 풀 수 있는 문제였다 ㅠㅠ

만약 i가 2라면?

 

temp='-'

[0] * 3 = [0,0,0]

위 배열의 크기만큼, 즉 i만큼 for문을 돌린다.

temp=temp + " "*len(temp)+temp

temp='-'+' '+'-' = '-  -'

temp='- -' + ' ' * len(temp) + '- -'= '- -   - -'

 

맨 아래부터 시작해서 점차 위로 올라가는 방식, 재귀함수랑 비슷한 맥락이다.

처음엔 - -이 temp에 들어간다.

그리고 temp의 길이, 즉 3만큼의 공백이 가운데 들어가고 공백 뒤에는 temp가 붙는다.

그러면 총 길이가 9인 - -   - -가 완성된다.

그리고 위와 같은 방식으로 - -   - - + 공백 9개 + - -   - -를 하게 되면

- -   - -        - -   - -가 출력된다.

 

 

처음부터 -값을 배열에 넣고 시작해서 더 어렵게 생각하게 된 것 같다.

이런 문제의 경우에는 N=1 , 즉 가장 마지막 단계부터 위로 거슬러 올라가면서

규칙이 있는지 살펴보는 게 좋을 것 같다는 생각이 든다.

(지극히 개인적인 의견)

 

import sys
for i in sys.stdin:
    temp="-"
    for j in range(int(i)):
        temp=temp+" "*len(temp)+temp
    print(temp)