[BOJ 2447, Python 3] 별찍기 - 10

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

2447번: 별 찍기 - 10

 

 

풀이

예제를 보면 $3^n \times 3^n$으로 된 정사각형에서 가운데가 텅 비어있고, $3^{n-1} \times 3^{n-1}$이 텅 비어있고, .... 이렇게 모든 정사각형에서 가운데가 텅 비어있는 정사각형을 그리는 것이 목표입니다.

 

그래서 분할정복을 사용하여 가운데를 공백으로 만들어주고 -> 이전 정사각형보다 세 배 작은 정사각형들의 가운데를 공백으로 만들어주고 -> 이전 정사각형보다 세 배 작은 정사각형들의 가운데를 공백으로 만들어주고... 이것을 정사각형의 길이가 3이 될 때까지 반복해주시면 됩니다.

 

 

코드

def go(last_x, last_y, length, fill):
    if fill:
        for x in range(last_x - length, last_x):
            for y in range(last_y - length, last_y):
                arr[x][y] = ' '
        return
    next_len = length//3
    if length >= 3:
        for i in range(3):
            for j in range(3):
                nx = last_x - next_len * i
                ny = last_y - next_len * j
                go(nx, ny, next_len, 1 if i == j == 1 else 0)
 
n = int(input())
arr = [['*'] * n for _ in range(n)]
go(n, n, n, 0)
for i in range(n):
    print(''.join(arr[i]))