[파이썬] 백준 #2447 별 찍기 - 10

첫 백준 골드 문제 입성!

---

문제

재귀적인 패턴으로 별을 찍어 보자. 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=3^k이며, 이때 1 ≤ k < 8이다.

27

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

---

풀이 과정

문제 조건에서도 재귀를 사용하라고 되어 있었고, N=3일 때의 블럭을 활용하는 것이 여러모로 편해보였다. 다 풀고 보니 훨씬 단순한 해결 방법이 생각났는데.. 왜 진작 못 떠올렸을까 싶기도 하다 ㅋㅋ

1. 재귀함수 counting_stars(N) 정의하기

def counting_stars(k):

    if k == 1:
        global arr
        arr = [['*'] * 3 for i in range(3)]
        arr[1][1] = ' '

    else:
        counting_stars(k-1)
       
        len_prev = (3 ** (k - 1))     # counting_stars(k-1)의 len
        len_pre_prev = (3 ** (k - 2)) # counting_stars(k-2)의 len

        for i in range(len_prev):
            arr[i] *= 3

        for i in range(2):
            for j in range(len_prev):
                arr.extend([arr[j][:]])

        for i in range(len_prev, 2*len_prev):
            for j in range(len_prev, 2*len_prev):
                arr[i][j] = ' '

    return arr

함수는 N이 아닌 k값을 사용하였다.
k = 1일 때, 재귀가 종료되며 3x3의 arr 값을 반환한다.
k = 1이 아닐 때, counting_stars(k-1)의 값을 옆으로 x3, 2번 extend한다.
마지막으로 전체를 9칸으로 봤을 때, 가운데 칸을 공백으로 바꿔주면 완성된다.

2. 입력값 설정하기

N = int(input())
for i in range(1, 8):
    if N == 3 ** i:
        k = i
        break

입력값 N을 받으면서 동시에 k값을 구해주었다.

3. 값 출력하기

counting_stars(k)
for i in range(N):
    for j in arr[i]:
        print(j, end = '')
    print()

위에서 구한 k값으로 재귀함수를 실행하고, arr의 원소를 출력한다.

- 답안

# counting_stars 재귀함수 정의
def counting_stars(k):

# 재귀 종료값. k=1일 때 3x3의 arr 생성
   if k == 1:
       global arr
       arr = [['*'] * 3 for i in range(3)]
       arr[1][1] = ' '

# 이전 값을 옆으로 x3, 2번 extend
# 전체를 9칸으로 봤을 때 가운데 칸 비워주기
   else:
       counting_stars(k-1)

       len_prev = (3 ** (k - 1))     # counting_stars(k-1)의 len
       len_pre_prev = (3 ** (k - 2)) # counting_stars(k-2)의 len
       
       for i in range(len_prev):
           arr[i] *= 3

       for i in range(2):
           for j in range(len_prev):
               arr.extend([arr[j][:]])

       for i in range(len_prev, 2*len_prev):
           for j in range(len_prev, 2*len_prev):
               arr[i][j] = ' '

   return arr

# 입력값 설정. N에 대한 k값을 구한다.
N = int(input())
for i in range(1, 8):
   if N == 3 ** i:
       k = i
       break

# 출력값 설정
counting_stars(k)
for i in range(N):
   for j in arr[i]:
       print(j, end = '')
   print()

---

*모든 문제의 저작권은 백준 온라인 저지(https://www.acmicpc.net/) 원작자에게 있습니다.
백준 2447번(https://www.acmicpc.net/problem/2447)