[Baekjoon 2447 / Python / 골드5] 별 찍기 - 10

문제

 

분할 정복 문제이다. 접근 순서가 작은 문제에서 큰 문제이든 큰 문제에서 작은 문제이든, 결국 작은 문제의 해결 방식이 큰 문제의 해결로 이어진다면 그것은 분할 정복이라고 할 수 있다. 매우 까다롭고 헷갈리는 문제였다.

 

 

# 분할 정복

import sys

input = sys.stdin.readline

N = int(input())

start = ['***', '* *', '***'] # N이 3일 경우의 초기 모양

def divideAndConquer(num, star):

    # 종료 조건

    if num == N:

        return star

   

    """

    이 반복문은 기존 star를 그대로 출력하는 것을 의미한다.

    따라서 3배 곱하여 append해주면 옆으로 3배 늘리는 것이 된다.

    for i in range(num):

        print(star[i])

    """

    tmpStar = []

    # 옆으로 3배 늘리는 작업을 3번 반복한다

    for i in range(num):

        tmpStar.append(star[i] * 3)

   

    # 가운데 부분은 공백으로 만든다

    for i in range(num):

        tmpStar.append(star[i] + ' ' * num + star[i])

   

    for i in range(num):

        tmpStar.append(star[i] * 3)

   

    return divideAndConquer(num * 3, tmpStar)

# 정답 출력

result = divideAndConquer(3, start)

for re in result:

    print(re)

 

N은 최소 3이기 때문에 N이 3일 경우의 모양을 미리 start 리스트에 담아 놓는다.

 

함수 내부에서 그때그때 출력할 경우 print의 개행 때문에 제대로 출력되지 않으므로, 리스트에 모양을 담아둔 후 마지막에 한번에 출력해 주어야 한다.

 

for i in range(num):

    print(start[i])

이 코드는 현재 별 모양을 한번 출력하는 것을 의미한다. 우리는 이 별 모양을 9배 크기로 늘려야 한다. 즉 이것을 9번 출력해야 한다. 무슨 뜻이냐면, 

 

9번 출력하기

 

이런 의미다. 기존의 별 모양을 9배로 늘림으로써 다음 별 모양이 완성된다. 물론, 가운데 부분은 공백으로 비워두어야 한다.

이것을 출력하는 방법은 이렇게 정의할 수 있다.

 

반복문 1 : 별 3번 출력 ( 3배 )

반복문 2 : 별 1번 출력 + 공백 + 별 1번 출력 ( 3배, 공백도 별 하나의 크기를 갖는다 )

반복문 3 : 별 3번 출력 ( 3배 )

 

옆으로 3배 늘리는 작업을 3번 반복함으로써, 기존 별 하나를 옆으로 3배 아래로 3배 늘린 효과를 가지게 됐다. 즉 9배다.

코드에서는 함수의 흐름을 위해 출력이 아니라 임시 리스트에 담아 두어야 한다. 그래서 append로 구현했다.

 

 

결과