[백준] 2447. 별 찍기 10
문제
패턴으로 별을 찍어보자. N이 3의 거듭제곱이라고 할 때, 크기 N의 패턴은 $N \times N$ 정사각형 모양이다.
크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
1
2
3
***
* *
***
N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 $(N/3) \times (N/3)$ 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.
입력
첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
출력
첫째 줄부터 N번째 줄까지 별을 출력한다.
예제 입력
1
27
예제 출력
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
********* *********
* ** ** * * ** ** *
********* *********
*** *** *** ***
* * * * * * * *
*** *** *** ***
********* *********
* ** ** * * ** ** *
********* *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
풀이
N=9일 때의 패턴은 다음과 같다.
1
2
3
4
5
6
7
8
9
*********
* ** ** *
*********
*** ***
* * * *
*** ***
*********
* ** ** *
*********
문제의 설명을 빌려 위 출력을 해석하면,
N=9의 패턴은
- 가운데의 $3\times 3$의 공백이 있다.
- 이 공백을 N=3일 때의 패턴으로 둘러쌓았다.
어떤 전략을 써야할지 감이 오는가? 바로 재귀함수이다.
사실 문제설명의 첫줄은 “패턴으로 별을 찍어보자”가 아니다. “재귀적인 패턴으로 별을 찍어보자”이다.
이렇게 문제 자체에 어떤 전략을 사용해야하는지 나와있다면 보다 답에 접근하기 쉽지만,
실제로는 그렇지 않은 경우가 많다. 따라서 왜 재귀 함수를 전략으로 사용하는것이 타당한지에 대해서
기준을 가지고 판단해야한다. 지난 하노이탑 문제에서와 마찬가지로, 재귀함수를 전략으로 사용할 수 있는지는 N일 때의 별을 찍는 Recurrent(N) 함수가 있을 때 Recurrent(N)이 수행되는 과정에서 Recurrent(N-1) 또는 Recurrent(N+1)이 수행되는지 확인해야한다.
하지만 이때 N은 3의 거듭제곱이기 때문에 Recurrent(N)이 수행될 때 Recurrent(N/3) 또는 Recurrent(N*3)이 수행되어야하는게 맞다.
위 N=9일 때의 예시를 보면, 가운데 있는 공백을 Recurrent(9/3), 즉 Recurrent(3)으로 둘러쌓은 것이다.
즉 Recurrent(N)을 수행하는 과정에서 Recurrent(N/3)이 수행된다. -> 재귀 함수를 전략으로 사용할 수 있다!
재귀식을 구체화하기전 생각해볼 것이 있다.
N=9일 때와 N=27일 때의 출력을 보면 각각 N/3의 패턴이 8번 찍히는 것을 확인할 수 있다.
즉 5번째에서는 별 패턴을 찍지 않고 (빈칸으로 놔두고), 나머지 1~4번째, 6~8번에 찍으면 N이 3의 거듭제곱일 때의 패턴이 전부 그려지게 된다.
이를 코드로 옮기면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
N = int(input())
paper = [[' ' for _ in range(N)] for _ in range(N)] # nxn matrix
def hew_star(n):
if n==3:
paper[0] = ['*'] * 3
paper[1] = ['*', ' ', '*']
paper[2] = ['*'] * 3
return
next_n = n // 3
hew_star(next_n)
#print(paper)
for col in range(0, n, next_n):
for row in range(0, n, next_n):
if col == next_n and row == next_n: # 이건 무슨의미?
continue
else:
for p in range(next_n):
paper[row+p][col:col+next_n] = paper[p][:next_n]
hew_star(N)
for i in range(N):
for j in range(N):
print(paper[i][j], end='')
print()