[Python] 백준 알고리즘 문제풀이 :: 2448번

몇 주를 고민했던 문제다. 프랙탈을 구현하는 문제. 쉬워보이면서도 막상 파이썬으로 구현하려고 하면 쉽지 않았던 문제다. 풀릴 듯 계속 안 풀리던 문제였는데 연휴에 하루 날 잡고 풀어버렸다. 백준 단계별 풀기를 처음부터 순서대로 쭉 풀다가 처음으로 막혀서 건너뛴 문제였다. 드디어 풀어버려서 기분이 좋다. 막상 마음먹고 고민하니깐 어렵지 않게 풀려서 희한했다. 풀 수 있다, 없다라는 마음가짐이 가져오는 결과의 차이를 보여주는 문제였다.

특히나 처음 시도했을 때와의 차이점은 재귀에 어느 정도 익숙해졌다는 것이다. 재귀를 말로만 들으면 쉬운데 막상 이를 활용해서 어떤 알고리즘을 구현하려면 생각만큼 쉽지 않다. 프랙탈 문제를 풀었다는 게 어느 정도 재귀를 활용할 수 있게 됐다는 증거라고 생각된다. 음 그리고 태도의 차이점이라면 내가 아는 것 내에서만 풀려고 하지 않았다는 것. 문제에서 로그값이 필요한데 뭔가 math 라이브러리에 있을 건 알았지만 가능한 내가 아는 내에서만 풀어보려고 했었다. 그냥 구글링으로 math 라이브러리로 로그 구하는 법 찾아서 시도하는 게 실마리였다.

문제

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

풀이

import sys
import math
 
lines = []
 
def starAdder(n, idx):
    stars = ["*", "* *", "*****"]
    k = round(math.log(n, 2) - math.log(3, 2))
 
    if idx == 0:
        for i in range(3):
            lines.append(stars[i])
    else:
        start = 6*(2**(idx-1))-1
        for i in range(0, len(lines)):
            space = " "*(start-2*i)
            s = lines[i] + space + lines[i]
            lines.append(s)
 
    if idx == k:
        return
    starAdder(n, idx+1)
 
n = int(sys.stdin.readline())
k = round(math.log(n, 2) - math.log(3, 2))
length = 6*(2**k)-1
 
starAdder(n, 0)
 
for i in range(0, len(lines)):
    ll = lines[i].center(length, " ")
    print(ll)

입력을 받아줄 sys 라이브러리와 로그를 구할 때 사용할 math 라이브러리를 호출한다.

lines는 출력할 각 줄의 문자열을 담을 리스트다. 즉 인덱스 0부터 삼각형의 첫번째 줄이다.

lines에 각 줄, 즉 별들을 담아줄 starAdder 함수를 생성한다. n은 줄의 개수고 idx는 현재 작업 중인 단계이다. 함수 실행시 첫 단계부터 만들어야 하므로 idx=0으로 설정해준다.

기본적으로 각 줄은 "*", " * * ", "*****"로 이루어져있다. 기본이 되는 이 세 문자열을 stars라는 리스트에 담는다.

k는 각 단계다. 줄이 3*2^k로 늘어나므로. 3 = 0단계, 6 = 1단계, 12 = 2단계 이런 식으로 생각하면 된다.

이제 본격적으로 줄을 만든다. 먼저 idx가 0이라면, 즉 별을 만드는 첫 시작 단계라면 그냥 stars에 있는 각 원소를 lines에 담아둔다. 이로서 n=3일 때, 즉 k=0일 때 1~3번줄이 완성된다. 출력해보면 3줄짜리 삼각형이 뜬다.

만약 idx==k이라면, 즉 현재 작업 중인 단계가 최종 목적 단계와 같다면 return함으로써 함수를 끝낸다. n이 3이었다면, k=0이고 idx도 0이므로 여기서 종료한다. 그러나 n이 3보다 크다면 아래 줄을 만들어줘야 한다. starAdder(n, idx+1)을 호출한다.

처음 설정한 idx가 0이었으므로, 두번째는 starAdder(n, 1)이 실행된다. idx는 0이 아니므로 else문으로 간다. start는 각 줄에서 두 문자열 사이의 공백이다. 각 단계는 바로 앞 단계까지 만들어진 삼각형을 좌우로 복사하는 모양을 가진다. 그리고 잘 살펴보면 각 줄에서 두 문자열 사이의 간격은 특정값부터 2씩 줄어들다. 그 특정값이 start이다.

바로 앞 단계 만들어진 삼각형의 줄 수, 즉 lines의 개수만큼 for문을 돌린다. space는 공백의 개수가 start부터 for문의 각 단계마다 2씩 줄어드므로 " "*(space-2*i)로 설정해준다. 그리고 lines[i] + space + lines[i]를 lines 리스트에 넣어준다. 이렇게 하면 바로 앞 단계까지 만들어진 삼각형이 두 개로 복사된다.

그리고 idx==k일 때, 즉 현재 작업 중인 단계가 목표 단계까지 왔을 때 return한다. 이러면 출력할 준비가 다 됐다. 이제 출력만 하면 된다.

출력도 마냥 하면 안 된다. 가운데 정렬을 해줘야 한다. 우선 n을 받고, 만들어질 삼각형의 마지막 줄의 칸 수인 length를 생성한다. 삼각형을 잘 살펴보면 알겠지만 k에 기반한 규칙성을 갖고 있다.

그리고 for문을 사용해 각 줄을 출력한다. 이 때 center() 함수를 사용한다. length만큼의 길이에서 가운데 정렬하고 빈 칸은 " "로 채운다는 의미이다. 출력하면 이쁜 프랙탈 삼각형이 나온다.