BOJ-2447

문제 주소

이 문제는 재귀적인 패턴으로 별을 찍는 문제로 문제의 입력에는 N이 3의 거듭제곱으로 나오게 된다. 일단 N = 3일 경우의 패턴은 다음과 같다.

***
* *
***

만약 N이 3보다 크다면 (N/3)의 패턴을 가운데는 뚫려 있도록 배치한 것이다.

따라서 N = 27일 경우 다음과 같은 패턴이 나오게 된다.

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

나는 이 문제를 패턴(N, 0, 0)이라고 단순화해서 보았다. 이때, 패턴(N, 0, 0)은 패턴 N을 좌상단 (0, 0)을 기준으로 보는 것이다.

패턴(N) ->

패턴(N/3,0,0)패턴(N/3,1*N/3,0)패턴(N/3,2*N/3,0)
패턴(N/3,0,1*N/3) (공백) 패턴(N/3,2*N/3,1*N/3)
패턴(N/3,0,2*N/3)패턴(N/3,1*N/3,2*N/3)패턴(N/3,2*N/3,2*N/3)

이런식으로 재귀 함수를 짜면 될 것이라 생각했다.

코드 작성

N = int(input())

A = ([" "] * N + ["\n"]) * N

먼저 N값을 받아주고 그다음 N값을 기초로 N*N 정사각형 같아 보이는 배열을 선언해준다. 여기선 일차원 배열인데 조금 새롭게 푸는 과정에서 이차원 배열을 일차원 배열로 변경했다.

def B(n, x, y):
    global A
    if n == 0:
        A[(N+1)*y+x] = "*"
        return
    c = n//3
    for i in range(3):
        for j in range(3):
            if i == 1 and j == 1:
                continue
            B(c, x+c*i, y+c*j)

그 다음 N = 0일 경우 배열의 공백을 "*"로 바꿔주고 아닐경우 재귀적으로 자신을 호출하는 함수를 만들었다. 중첩 for문으로 가운데 일 경우는 다음으로 넘겨버리고 아닐경우는 호출할 수 있도록 했다.

B(N, 0, 0)
for i in A:
    print(i, end="")

그런 먼저 말했던 B(N, 0, 0)을 호출하고 정답에 맞게 바꾼 배열을 for문을 통해 print한다.

결론

python으로 채점을 받아보니 시간 초과가 난 점이 조금 걸린다. pypy로는 시간초과가 안나고 잘 통과됐으니 맞은거겠지?. 이렇게보니 pypy랑 python이 시간차가 꽤 있다는게 좀 신기했다.

알고리즘을 수정해 python으로도 수월하게 넘어갈 수 있는 코드를 작성해봐야겠다. 아마 루프를 이용하면 될 것 같다.