[BOJ][Python]2448 풀이

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

2448번: 별 찍기 - 11

def recur(n):
    if n == 3:
        return ['  *  ', ' * * ', '*****']
    else:
        half = n//2
        before = recur(half)
        result = ['' for _ in range(n)]
        for i in range(half):
            result[i] = ' '*(half) + before[i] + ' '*(half)
        for i in range(half, n):
            result[i] = before[i-half] + ' ' + before[i-half]
        return result

n = int(input())
ans = recur(n)
for i in ans:
    print(i)

예전에 제가 재귀를 어렵다고 생각하게 했던 주범입니다. 저는 다른 재귀는 그래도 어찌어찌 머리로 풀겠는데 이런 프랙탈 구조 문제는 도통 이해가 안되더라구요. 이번에는 풀이 없이 풀었으니 그 때보다 성장했나봅니다.

 

제가 찾아낸 규칙은 다음과 같습니다. n이 3일 때의 형태를 기본형 A라고 치환했을 때,

n이 6일 때,

[][][]    [][][]

[][][] A [][][]

[][][]    [][][]

       []      

  A   []   A  

       []        

의 형태로 n//2의 형태가 총 3개가 나오면서 위에서는 n//2*n//2의 공백을 좌우에 두고 하나가, 아래에서는 좌우에 n//2의 형태를 두고 가운데에 한칸의 공백이 n//2번 나옵니다.

 

따라서 n이 3일 때는 그냥 기본형을 반환하고 그 이외에는 n//2번의 형태를 재귀 호출을 통해 반환받아서 반복문으로 원하는 형태가 되도록 만들어주면 됩니다. 다만 제가 구현한 방법 외에도 다양한 방법이 있습니다. 다른 분들의 규칙이나 식을 찾아보는 것은 여러분들의 즐거움으로 남겨두도록 하겠습니다.