[Python] 백준 2447번 : 별 찍기 - 10

Problem

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

Solution

위 문제는 분할정복 알고리즘을 통해 풀 수 있다.

• 분할 정복 분할 정복은 크게 분할-정복-병합 3단계로 나뉜다. 각 단계에서는 문제를 쪼갤 수 있는 최소 단위로 나눈 후, 각 최소 문제를 해결하고, 전체 문제로 합치는 과정을 거친다.

다시 위 문제로 돌아오면 문제는 3의 거듭제곱 꼴인 n값이 입력된다. 최종 출력할 별의 형태는 n x n 크기의 정사각형에 가운데에 n/3 만큼의 빈 공간이 있고 주변을 이루는 n/3 - 1개의 정사각형은 가운데에 n/3² * n/3² 만큼의 빈 공간이 있는 프랙탈 형태를 띈다.

따라서 제일 작은 단위인 n=3일 때의 형태. 즉, 아래와 같은 형태를 기저 단계(base case)로 저장해 두고 크기를 줄여서 해결해 나가면 된다.

***
* *
***

code

import sys

def makeStar(n):
    # 기저 사례
    if n == 3:
        return ['***','* *','***']

    finalStar = []
    beforeStar = makeStar(n//3) # 이전 별 모양

    # 위, 아래 패턴
    topStar = []
    for i in range(n//3):
        lineStar = beforeStar[i]*3
        topStar.append(lineStar)

    # 중간 패턴
    midStar = []
    for i in range(n//3):
        lineStar = beforeStar[i]+ ' '*(n//3) + beforeStar[i]
        midStar.append(lineStar)

    finalStar.extend(topStar) # 윗 줄
    finalStar.extend(midStar) # 가운데 줄
    finalStar.extend(topStar) # 아래 줄

    return finalStar

n = int(sys.stdin.readline())

result = makeStar(n)
print('\n'.join(result)) # 요소를 줄 바꿔 출력

Memo

리스트를 활용한다는 사실을 알기 전까지는 해결하기가 정말 어려웠다.

Ref.

https://velog.io/@ember/분할정복-백준-2447-별-찍기-10
https://ko.wikipedia.org/wiki/분할_정복_알고리즘
https://abouteverything.tistory.com/10