재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.
크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
***
* *
***
N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.
첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
첫째 줄부터 N번째 줄까지 별을 출력한다.
입력 1
27
출력 1
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
********* *********
* ** ** * * ** ** *
********* *********
*** *** *** ***
* * * * * * * *
*** *** *** ***
********* *********
* ** ** * * ** ** *
********* *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
당황스럽다. 여러가지 아이디어가 떠올랐는데 가운데 커다란 구멍을 어떻게 할지 떠오르지 않았다. 규칙을 만들어서 적용을 해야겠다는 생각을 하였다.
기본적으로 입력에 대해 3으로 나눠가면서 진행한다 예, 27 -> 9 -> 3 -> 1 ( 1이 되면 종료 )
-
if size == 1:
- 1이 되면 종료
-
stars = append_star(size//3):
- 현재 크기의 1/3 크기의 작은 별 패턴을 생성하기 위해 자기 자신을 재귀적으로 호출
-
for s in stars: board.append(s*3):
-
for s in stars: board.append(s+' '*(size//3)+s):
-
for s in stars: board.append(s*3):
- 아래를 예시를 보는게 이해가 빠를 것 같다.
- 아래 예시에서 9->27 갈 때에는 9까지 만들어놓고 27에서는 3번씩 출력한다고 생각하면 된다.
- s+' '*(size//3)+s 여기서 공백과 함께 출력한다.
-
1 ['*']
-
3 ['', ' ', '']
-
9 ['', ' ** ** ', '', '*** ', ' * * ', ' ', '', ' ** ** ', '***']
-
27
재귀가 일어날 때 하나씩 차근 차근 패턴을 찾으면 좋을 것 같다. 한단계, 두단계 반복하는 패턴을 찾으면 나머진 금방 찾을 수 있을 것 같다.
import sys
sys.setrecursionlimit(10**6)
def append_star(size):
if size == 1:
return ['*']
stars = append_star(size//3)
board = []
for s in stars:
board.append(s*3)
for s in stars:
board.append(s+' '*(size//3)+s)
for s in stars:
board.append(s*3)
return board
n = int(sys.stdin.readline().strip())
print('\n'.join(append_star(n)))