[백준 BOJ_2447] 별 찍기 - 10 Python 풀이

출처: 백준 온라인 저지

문제

풀이 1

분할 정복 알고리즘을 이용하여 풀어보겠습니다.

분할 정복: 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고 다시 합병하는 방법

N=27이라면 27*27을 9*9로, 9*9를 3*3로, 3*3을 1*1까지 분할시킬 수 있습니다.

아래는 3*3의 사각형의 빈 곳의 좌표(y, x)를 표시한 N=9의 윗부분 출력입니다.

*********
* ** ** * (1, 1) (1, 4) (1, 7)
*********

3*3 사각형의 경우는 y나 x의 값이 1, 4, 7 … 3m + 1일 때에만 빈 칸을 출력합니다.
다른 말로는 y나 x를 3으로 나누었을 때 나머지가 1일 경우에만 빈 칸을 출력합니다.

• y % 3 = 1, x % 3 = 1

아래는 9*9의 사각형의 빈 곳의 좌표를 표시했습니다.

*********
* ** ** *
********* 
***   ***  (3, 3) (3, 4) (3, 5)
* *   * *  (4, 3) (4, 4) (4, 5)
***   ***  (5, 3) (5, 4) (5, 5)
*********
* ** ** *
*********

9*9 사각형은 y나 x를 3으로 한번 나눈 뒤의 값의 나머지가 1일 경우에 빈 칸을 출력합니다.

• (y // 3) % 3 = 1, (x // 3) % 3 = 1

기저 사례는 y와 x를 3으로 나눌 때 나머지가 1일 때는 빈 칸(“ “)을, N이 1일 때는 가장 작은 사각형일 때이기 때문에 별(“*“)을 출력해줍니다.

그 뒤로는 y, x, n을 모두 3을 나눈 값으로 재귀호출을 해줍니다.

코드 1

def draw_star(y, x, n):
    if y % 3 == 1 and x % 3 == 1:
        print(" ", end="")
    elif n == 1:
        print("*", end="")
    else:
        draw_star(y // 3, x // 3, n // 3)
    
N = int(input())
for y in range(N):
    for x in range(N):
        draw_star(y, x, N)
    print()

풀이 1은 Output에는 문제없으나 아무래도 Python에서는 시간초과가 되었습니다.

풀이 2

Python으로 구현하고 싶은 욕심에 이것 저것 시도해 보았지만 도저히 어떻게 구현해야 될지 감이 안잡혀 구글링하는 도중 가장 이해가 되는 풀이를 찾을 수 있었습니다. 아래 링크의 3번째 풀이입니다.

풀이 출처 링크

예시를 들어 나름대로 해석해보겠습니다.

사각형을 윗 부분, 중간 부분, 밑 부분으로 나누어서 별을 찍어 주는 방법입니다.

• 윗 부분은 (N//3)*(N//3)사각형을 3번 반복
• 중간 부분은 (N//3)*(N//3)사각형을 1번, (N//3)*(N//3)만큼 비워주고 다시 (N//3)*(N//3)사각형을 1번
• 밑 부분은 윗 부분과 동일

N=3일 때 block, top, mid의 값은

block = ["*"]
top = ["***"] # "*" * 3 = "***"
mid = ["* *"] # "*" + " " * (3//3) + "*" = "* *"

N=9일 때는

block = ["***", 
         "* *", 
         "***"]
top = ["*********", # "***" * 3 = "*********"
       "* ** ** *", # "* *" * 3 = "* ** ** *"
       "*********"] # "***" * 3 = "*********"
mid = ["***   ***", # "***" + " " * (9//3) + "***" = "***   ***"
       "* *   * *", # "* *" + " " * (9//3) + "* *" = "* *   * *"
       "***   ***"] # "***" + " " * (9//3) + "***" = "***   ***"

패턴이 보이기 시작합니다.

기저 사례는 더 이상 분할이 되지 않을 때인 N=1일 때 별(“*“)하나를 가진 리스트를 반환해줍니다.

그 뒤로는 N을 3으로 나눈 값으로 재귀 호출을 해줍니다.

마지막에는 윗 부분, 중간 부분, 밑 부분의 리스트를 합친 리스트를 반환해줍니다.

• top + mid + top

코드 2

def draw(n):
    if n == 1:
        return ["*"]
    block = draw(n//3)
    top = [ b * 3 for b in block ]
    mid = [ b + " " * (n//3) + b for b in block ]
    return top + mid + top
    
N = int(input())
print("\n".join(draw(N)))