https://www.acmicpc.net/problem/2447

문제 접근

이전에 풀어보려고 시도했던 문제로 일단 그림을 그려보면서 규칙을 찾기 위해서 노력했다. 아래 그림처럼 일단 별을 많이 그려보고 3X3의 패턴을 기본단위로 생각하기로 했다.

좌표로 나타냈을 때 1,1만 비우면 3X3의 패턴을 만들 수 있고, 9X9패턴도 3X3으로 이루어진 3X3 패턴으로 생각했을 때 마찬가지로 1,1에 해당하는 좌표를 비우면 만들 수 있음을 확인했다.

첫 번째, 두 번째 시도

접근에서 고민했던 내용들을 어떻게 식으로 표현할까를 고민했다. 다음과 같이 좌표를 (i, j)로 표현했을 때 3으로 나눈 나머지 중 하나가 1일 때 비우기로 했다.

또 9 이상의 패턴일 때 가운대를 비워주기 위하여 3으로 나눈 후에 3으로 나눴을 때 나머지가 1인 경우에 빈 칸을 출력하도록 바꾸어서 아래와 같은 코드를 만들었다.

def solve(i, j):
    if i % 3 == 1 and j % 3 == 1:
        print(" ", end="")
    elif (i//3) % 3 == 1 or (j//3) % 3 == 1:
        print(" ", end="")
    else:
        print("*", end="")

N = int(input())
for i in range(N):
    for j in range(N):
        solve(N, i, j, 1)
    print()

하지만 27 이상 부터는 제대로 작동을 하지 않아서 무엇이 문제인지 분석을 해보았다.

세 번째 시도

결국에는 인터넷 검색을 몇 번 해보니까 이 문제와 같이 같은 모양이 반복되는 구조를 프렉탈구조라 말하며 이런 문양의 경우에는 재귀함수로 쉽게 구현을 할 수 있다고 한다. (생각해보니 파이썬 처음 배울 때 Turtle 패키지로 비슷한 문양을 만들었던 기억이 났다.) 이 점을 착안해서 지금 구현한 내용을 재귀함수 형식으로 바꿔보았다.

Turtle로 프랙탈 구조를 만들었던 경험을 바탕으로 생각해보면 도형의 길이를 scale로 표현하여 scale을 점점 키워나가는 형태로 접근하여 아래와 같은 코드를 작성했다.

def solve(N, i, j, scale):
    if (i//scale) % 3 == 1 and (j//scale) % 3 == 1:
        print(" ", end="")
    elif N == scale:
        print("*", end="")
    else:
        solve(N, i, j, scale * 3)


N = int(input())
for i in range(N):
    for j in range(N):
        solve(N, i, j, 1)
    print()

결과는 Python3로 채점했을 때는 Timeout이 나왔지만 PyPy3로 채점 시 성공을 할 수 있었다. 그런데 PyPy3로 채점했을 때만 성공한다는 것은 뭔가 최적화를 더 할 수 있다는 뜻이 아닐까 싶은데.. 아직은 내공이 부족해서 그런지 어떤 점을 고쳐야할지 잘 모르겠다. 이후에 푼 문제들을 쭉 리뷰하면서 다시 한 번 살펴보면 좋을 것 같다.