[BOJ] 2447번 별 찍기 - 10

[BOJ] 2447번 별 찍기 - 10 문제

매우 어려운 재귀 문제다. 뉴비 절단기 삼대장 중 하나답게 매우 어렵다.

재귀는 삼대장 중 하나일 뿐이지

---

재귀의 핵심은 반복되는 부분을 코드로 압축시키는 것이다. 먼저 이 문제에서는 어떻게 반복되는지를 살펴보자.

먼저 $ 1 \leq k < 8  $이지만 $ k = 0 $의 경우도 있다고 치자. 그렇다면 $ k = {0, 1, 2} $일 때의 패턴은 아래와 같다.

# k == 0
*

# k == 1
***
* *
***

# k == 2
*********
* ** ** *
*********
***   ***
* *   * *
***   ***
*********
* ** ** *
*********

 

패턴이 보이는가? $ k \geq 1 $부터 $ k $번째 패턴에서의 첫 $ 3^{k-1} $줄에는 $ k-1 $번째 패턴이 세 개 들어가 있고, 두 번째 $ 3^{k-1} $줄에는 $ k-1 $에서의 패턴 / $ 3^{k-1} $개의 빈칸 / 다시 $ k-1 $에서의 패턴이 들어가고, 마지막 $ 3^{k-1} $줄에서는 첫 $ 3^{k-1} $줄과 같은 패턴을 보여준다.

이를 코드로 옮기면 된다...!

---

import sys

def recur(n):
    if n == 1:
        return ['*']

    recur_star = recur(n//3)
    now_star = list()
    for now_recur_star in recur_star:
        now_star.append(now_recur_star*3)
    for now_recur_star in recur_star:
        now_star.append(now_recur_star + ' '*(n//3) + now_recur_star)
    for now_recur_star in recur_star:
        now_star.append(now_recur_star*3)

    return now_star

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    star = recur(N)
    print(*star, sep='\n')

 

실제로 이 문제는 재귀의 정점에 다가가야만 겨우 풀 수 있는 문제 중 하나로 손 꼽히고 있다.

최종적으로 구할 star는 main쪽에 두고, 재귀 부분을 함수 안에 집어넣는 것이 핵심이다.

만약 재귀가 이해되지 않는다면 이 문제는 제껴두는 것을 강권하고 쉬운 재귀 문제부터 풀 것을 추천한다.