[PS][BOJ/2447번]-별 찍기 - 10

문제 설명

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

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

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

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

출력

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

문제 분석 과정

문제의 예시를 통해 유추하는게 중요한 문제이다.

첫 번째 예시
n = 3 일 때

***
* *
***

두번째 예시
n = 27 일 때

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

해당 예시를 살펴보자 n=3 일 때 형태가 Default-Form 이 되고, F(3)
이라고 하자. n = 9 일 때를 먼저 파악해보자. F(n)은 가운데가 뚫려있는 모양이다. n = 27 일 때의 규칙을 미뤄 보았을때 n = 9 의 형태는 다음과 같다.

*********        
* ** ** *        
*********        
***   ***        
* *   * *      
***   ***      
*********        
* ** ** *         
*********

n = 9일때는 F(F(3))이라고 볼 수 있다. 그럼 마찬가지로 n = 27 은
F(F(F(3)))으로 표현되고 이를 일반화하면 아래와 같다.

점화식

$$
if \quad n=3^1, \qquad F(3)
$$
$$
if \quad n=3^2, \qquad F(3^2) = F(F(3))
$$
$$
if \quad n=3^3, \qquad F(3^3) = F(F(F(3)))
$$
$$
if \quad n=3^k, \qquad F(3^k) = F(F...(F(3)))
$$

위 수식을 통해 재귀적으로 구성되어있음을 알았다.

사실 처음 이 문제를 풀었을 때 일반적인 for문 별 찍기 문제처럼 규칙을 찾아 조건 작성해 해결하려했지만 이 문제는 그렇게 해결 되지않는다(재귀적으로 이뤄져있기 때문).

문제를 관성적으로 해결하려했던 것을 반성하며, 코드 작성을 해보자.

1. 문제를 해결하기 위해 빈리스트에 기본폼을 작성한다.
2. 부모 박스안에 자식박스가 있고 두 박스 모두 Default-Form을 따른다.
3. 자식박스를 이루는 요소 * 3 = 부모박스를 이루는 요소

위 과정에 따라 코드를 작성하면 아래와 같다.

소스 코드

import math
n = int(input())

# n : 3 의 거듭제곱

# on  on  on
# on  off on
# on  on  on

# n =3^k 일 때 다음 처럼 찍힌다.

# 3^(k-1)  3^(k-1)  3^(k-1)
# 3^(k-1)    off    3^(k-1)
# 3^(k-1)  3^(k-1)  3^(k-1)

# 00 01 02
# 10    12
# 20 21 22

# 00 01 02 03 04 05 06
# 10    12 13    15 16
# 20 21 22 23 24 25 26
# 30 31 32          36
# 40    42          36
# 50 51 52          56
# 60 61 62 63 64 65 66

star = ["***", "* *", "***"]

def makeStar(n):
    # 기본세트
    if n == 3:
        return star

    # 최종완성본을 저장할 리스트
    result = []

    # k 번째 일떄 k-1 의번째 세트를 xStar 초기화
    xStar = makeStar(n//3)

    # 크게 볼 때 0 행 
    for sub in xStar:
        # 3번 불러옴
        result.append(sub*3)

    # 크게 볼 때 1 행
    for sub in xStar:
        result.append(sub + " "* (n//3)   +sub)
    # on of on
    # ononon offoffoff ononon

    # 크게 볼 때 2 행
    for sub in xStar:
        # 3번 불러옴
        result.append(sub*3)
    return result


print("\n".join(makeStar(n)))

문제 원본
소스코드 원본

오류나 질문에 대한 문의 댓글로 남겨주겨주세요!