문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, …)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

www.acmicpc.net/problem/2447

  • 입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

  • 출력

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

과정

앞선 종이의 개수 문제와 비슷하다고 생각해서 크기를 9등분으로 나눠가면서 중간을 제외한 8칸에 재귀함수를 호출하여 별을 출력하는 방법을 사용했다.

하지만 결과는 시간 초과였다. 종이의 개수 문제에서는 9등분한 9칸을 각각 확인하여 [-1, 0, 1] 중 어떤 수로 채워져 있는지를 각각 확인해야 했지만 이 문제에서는 확인하는 절차 없이 바로 별을 찍으면 된다. 그렇기 때문에 재귀함수를 8번이나 호출해서는 시간을 맞출 수가 없다.

import sys

def dnc(x, y, n):
    if n == 1:
        arr[x][y] = '*'
        return

    for i in range(x, x+n):
        for j in range(y, y+n):
            n //= 3
            dnc(x, y, n)
            dnc(x, y + n, n)
            dnc(x, y + 2 * n, n)
            dnc(x + n, y, n)

            dnc(x + n, y + 2 * n, n)
            dnc(x + 2 * n, y, n)
            dnc(x + 2 * n, y + n, n)
            dnc(x + 2 * n, y + 2 * n, n)

n = int(sys.stdin.readline().strip())
arr = [[' ']*n for _ in range(n)]

dnc(0, 0, n)

for line in arr:
    for x in line:
        print(x, end="")
    print()

최종 코드

재귀함수를 8번이 아니라 1번만 호출해서도 이 문제를 해결할 수 있다.

재귀함수에서 칸의 크기인 n을 받는다. 그리고 n을 3으로 나누어 재귀함수를 호출한 뒤 그 값을 stars에 저장한다.

그럼 stars에는 9등분된 한 칸에 들어갈 별의 출력이 저장되어 있을 것이다. 이것을 순서대로 첫 번째 줄에 3번 복사하고, 두 번째 줄에는 중간을 비우고 2번만 복사하고, 세 번째 줄에도 첫번째 줄과 같이 3번 복사한다.

이런식으로 코드를 짜면 시간을 훨씬 줄일 수 있다.

import sys

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

    stars = dnc(n//3)
    ret = []

    for s in stars:
        ret.append(s * 3)
    for s in stars:
        ret.append(s + ' ' * (n//3) + s)
    for s in stars:
        ret.append(s*3)
    return ret

n = int(sys.stdin.readline().strip())
arr = dnc(n)
print('\n'.join(arr))

참고 사이트