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

 

4779번: 칸토어 집합

 

def cant(a,s,length):
    temp = length //3
    if temp == 0:
        return a

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

    cant(a,s,temp)
    cant(a,s+temp*2,temp)

    return a

N = int(input())
array=['-']*(3**N)
print(''.join(cant(array,0,len(array))))

 

먼저, -가 3**N 개 있는 문자열에서 시작한다고 했으니까 초기값으로 정의 해주고 

만약에 N 이 3이라면 문자열 length는 27이니까 27을 3등분하면 9 그러면 9에서 또 3등분을 하고 ...

암튼 3으로 나눴을때 몫이 0 이면 재귀를 멈추면 된다라고 먼저 생각했다. 

그리고 공백을 기준으로 2갈래씩 나뉘니까 재귀를 두번 호출해줘야겟군,, 까지 생각함 

나눠준 지점부터 길이만큼 공백으로 만드는 반복문을 넣어주고

만약에 처음 length가 27이면 가운데 값은 9부터 18 이니까 가운데를 제외한 양쪽을 계속 나눠가면서 공백으로 바꿔주고 

배열 리턴하면 끝 

 

근데 틀렷슴다 작렬 .,.,.,.,.우띠 

 

# 칸토어 집합

def cant(a,s,length):
    temp = length //3
    if temp == 0:
        return a

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

    cant(a,s,temp)
    cant(a,s+temp*2,temp)

    return a
while True:
    try:
        N = int(input())
        array = ['-'] * (3 ** N)
        print(''.join(cant(array, 0, len(array))))
    except: #EOF 발생
        break

 

문제에서 입력을 여러 줄로 이루어져있다. 했기 때문에 무한 반복으로 입력을 받는다. 

혹시라도 EOF 에러가 발생한다면 프로그램을 종료하도록 try - except 구문을 넣어줘야 한다고 한다 핳 

 

사실 이 문제가 재귀 문제 시리즈에서 봐서 재귀로 풀어야징 하는 생각이 있었는데 

재귀로 풀지 않더라도 규칙을 찾아내면 풀 수 있다. 

결과는 무슨 숫자가 들어가든 처음 시작은 "- -"일 수 밖에 없다. 

temp = "- -"라고 하고

만약 N이 2라면 

총 길이가 9 인 "- -   - -"가 나온다. (공백3개) 

만약에 N이 3이라면

총 길이가 27인 "- -   - -         - -   - -" 가 나오게 된다. (공백 9 개) 

코드로 만들면 

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

 

차라란 

 

첨엔 가운데를 잡아서 대칭 시켜버릴가 했는데 

제출은 아주아주 번거로운 방식으로 했던 것같다. 

시험볼때마다 엄청 긴장하는 타입이라 코테볼때는 얼어서 생각 못했을 것 같다. 

쩝 

거기서도 생각해내려고 공부하는거니까 ^^* 

아쟈아쟛