[BOJ / 파이썬] 2447번: 별 찍기 - 10

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

단계 : 재귀

알고리즘 분류 : 분할정복, 재귀

 

풀이:

 사각형을 9등분했을 때 가운데를 공백으로 비워두는 것이 문제의 목적이다. n*n 크기의 정사각형 리스트를 만들어 둔 후 n은 3의 거듭제곱이라 하였으니 n을 기준으로 중심을 계산해서 공백을 넣는 방식으로 풀면 된다. 재귀 형탠는 작업을 할 정사각형의 왼쪽 위 좌표와 정사각형 한 변의 길이를 넘겨주는 방식으로 진행한다.

 

예를 들어 27의 정사각형을 작업할 때는 27*27의 중앙을 공백으로 바꾼 후 9개의 9*9 꼴의 정사각형으로 다시 나누어 각 정사각형마다 중앙을 공백으로 나눈다. 이미 공백으로 바뀐 곳은 *로 만들어 주는 부분이 재귀함수에 존재하지 않기 때문에 그대로 공백으로 남아있을 것이며 정사각형 한 변의 길이가 3이 될 때 가운데를 공백으로 만들어주고 재귀를 종료한다.

 

코드

def rect_star(x, y, n, ls):
    if n == 3:
        ls[x + 1][y + 1] = " "
    else:
        temp = n // 3
        for i in range(x + temp, x + 2 * temp):
            for j in range(y + temp, y + 2 * temp):
                ls[i][j] = " "
        for i in range(0, n, temp):
            for j in range(0, n, temp):
                rect_star(x + i, y + j, temp, ls)


n = int(input())
ls = [["*" for i in range(n)] for i in range(n)]

rect_star(0, 0, n, ls)
for i in range(0, n):
    for j in range(0, n):
        print(ls[i][j], end="")
    print()