[백준] 2447 별 찍기 - 10 (파이썬)

문제

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

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

***
* *
***

입력

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

출력

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

알고리즘 아이디어

1. '*'로 채워진 nxn 크기의 배열을 만든다
2. n == 3 이라면 가운데만 공백으로 바꾼다
3. n > 3 이라면 전체 배열을 9칸으로 나누고 가운데 칸은 공백으로 바꾸고 나머지 칸에 대해서 재귀적으로 실행한다

전체 nxn 배열을 9개의 부분문제로 나눠 해결할 수 있다. n == 3인 경우가 베이스 케이스로 중앙을 제외한 각 부분(칸)은 n == 3이 될때까지 재귀적으로 실행한다

알고리즘

def main():
    n = int(input())
    grid = [['*' for _ in range(n)] for _ in range(n)]
    unmarkStars(grid, n, (0,0))
    printGrid(grid)

# start_point : 최좌상단 좌표
def unmarkStars(grid, n, start_point):
    x, y = start_point
    # 베이스 케이스 : 가운데 별 제거
    if n == 3:
        grid[x+1][y+1] = ' '
        return

    # 가로 세로 3등분, 9칸으로 나눔
    for i in range(0, n, n//3):
        for j in range(0, n, n//3):
            start_point = (x + i, y + j)
            # 가운데 칸은 공백으로 바꿈
            if i == n//3 and j == n//3:
                emptyCenter(grid, n, start_point)
            # 나머지 칸은 재귀적으로 각 칸에 대해 실행
            else:
                unmarkStars(grid, n//3, start_point)

def emptyCenter(grid, n, start_point):
    x, y = start_point
    for i in range(x, x + n//3):
        for j in range(y, y + n//3):
            grid[i][j] = ' '

def printGrid(grid):
    for i in range(len(grid)):
        print(''.join(grid[i]))

if __name__ == "__main__":
    main()

시간복잡도

점화식

f(n) = 1           if n == 3
     = 9 * f(n//3) if n != 3

시간복잡도 분석

T(n) = 3^2 * T(n/3)
     = 3^2 * (3^2 * T(n/3^2)) = 3^4 * T(n/3^2)
     = 3^2k * T(n/3^k)
     if n/3^k = 3, 3^k = n/3
     = n/3*n/3 * T(3) = n^2/9 * 1
     : O(n^2)