[BOJ 2447] 별 찍기 - 10 (Python)

---

문제

별 찍기 - 10

---

문제 해설

주어진 N을 이용해 별을 찍는 문제입니다.
문제는 간단하지만 구현하는 내용이 어렵습니다. N은 3^7 = 2187까지 입니다.

처음에 시도했던 방법은 재귀를 이용해 매개변수로 저장된 리스트를 넘겨줘서 depth가 N의 3제곱근이면 return 하게 구현했지만, 시간초과와 더불어 메모리초과까지 겪었습니다.
아무래도 deepcopy와 함께 리스트를 그냥 더하는 방식으로 구현했기 때문에 발생한 것 같습니다.

다음에 시도한 방법은 처음부터 N x N 리스트를 "*" 로 초기화 하는 방식입니다.
코드를 보시면 5중 for문이라 시간이 오래걸릴 것이다 라고 생각하시겠지만, 시간복잡도는 정확히 K*9^(K-1) + N^2만큼이 걸립니다.

N^2 는 전체탐색에 대한 시간이고 K*9^(K-1)는 K에 대하여 "*"를 빈칸으로 만드는데 필요한 시간입니다.
N = 3^1

빈칸으로 만들기 위한 연산 = 1

---

N = 3^2

빈칸으로 만들기 위한 연산 = 1*9 + 3*3

---

N = 3^3

빈칸으로 만들기 위한 연산 = 1*9*9 + 3*3*9 + 9*9

따라서 식을 세우게 되면 K*9^(K-1) 이므로 제한 시간안에 해결할 수 있습니다.

---

시간, 메모리 초과 코드

import copy


def dfs(depth, goal, iterator):
    if depth == goal:
        for i in range(len(iterator)):
            print("".join(iterator[i]))
        return
    size = len(iterator)
    for i in range(size):
        temp = copy.deepcopy(iterator[i])
        for j in range(2):
            iterator[i] += temp
    for i in range(2):
        for j in range(size):
            temp = copy.deepcopy(iterator[j])
            iterator.append(temp)
    for i in range(size, size * 2):
        for j in range(size, size * 2):
            iterator[i][j] = " "
    dfs(depth + 1, goal, iterator)


dfs(0, int(int(input()) ** (1 / 3)), [["*"]])

---

풀이 코드

n = int(input())
graph = [["*" for _ in range(n)] for _ in range(n)]
temp = n
k = 0
while True:
    if temp == 1:
        break
    temp //= 3
    k += 1
for i in range(k):
    pos = 3 ** i
    for a in range(0, n, pos * 3):
        for b in range(0, n, pos * 3):
            for i in range(pos + a, pos * 2 + a):
                for j in range(pos + b, pos * 2 + b):
                    graph[i][j] = " "
for i in range(n):
    for j in range(n):
        print(graph[i][j], end="")
    print()

---