[PS][BOJ/2448번]-별 찍기 - 11

문제 설명

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

예시 - 1

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

입력

첫째 줄에 N이 주어진다. N은 항상 3×2^k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)

출력

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

문제 분석 과정

이 문제는 지난번 포스팅한 [PS][BOJ/2447]- 별 찍기-10 와 완전히 동일하다고 볼 수있다.
모양새에 겁먹어서는 안된다. 가장 작은 삼각형을 살펴보아서 Default-Form을 찾고 규칙을 찾는 과정을 갖는다.
n = 3 일 때, 모양새는 아래와 같다.

  *                        
 * *                       
*****  

이 문제가 [PS][BOJ/2447]- 별 찍기-10 와 동일한 이유는 Default-Form 의 형태 때문이다. 삼각형 처럼 보이긴 하지만 Default-Form 을 구성하는 방식은 아래와 같기 때문이다.

null null \* null null
null  \* null \* null
\*****

해당 모형은 크기가 3X5 인 2차원 배열로 볼 수 있고 그럼 이전 문제와 완전히 동일해 지는 것이다.

이전 포스팅을 보지않았거나 아직 이해가 안되었을 수 있으니 하나의 예시를 더 들어서 설명해보겠다.
다음은, n = 6 일때 모형이다. 가운데 부분에 생기는 모양을 신경쓰지말고
직사각형으로 생각해 보면 된다. 윗 층에는 3X5 인 2차원 배열이 한 개가 있는것이고 아래 층에는 3X5 인 2차원 배열이 두 개가 있는 것이다.

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

점화식

$$
if \quad n = 3*2^1,\ F(3*2^1) = F(F(3*2^0))
$$

$$
if\quad n = 3*2^2,\ F(3*2^2) = F(F(3*2^1)) = F(F(F(3*2^0)))
$$

$$
if\quad n = 3*2^3 ,\ F(3*2^3) = F(F(3*2^2)) = F(F(F(3*2^1))) = F(F(F(F(3*2^0))))
$$

$$
if\quad n = 3*2^k , \ F(3*2^k) = F(F(3*2^{k-1})) = F(F(F(3*2^{k-2}))) = F(F(...F(F(3*2^0))))
$$

해당 점화식을 찾고 [PS][BOJ/2447]- 별 찍기-10 동일한 과정으로 코드를 작성하면 아래와 같다.

소스 코드

import sys
input = sys.stdin.readline

n = int(input())


# n : 3 * (2 의 거듭제곱)

# k = 0
# (공백 2) 별 (공백 2)
# (공백 4) 별 (공백 4)
star = ["  *  ", " * * ", "*****"]


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

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

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

    # 크게 볼 때 0 행
    for sub in xStar:
        # 1번 불러옴
        result.append(" "*3*((n//3)//2) + sub + " "*3*((n//3)//2))

    # 크게 볼 때 1 행
    for sub in xStar:
        result.append(sub + " " + sub)

    return result


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

문제 원본
소스코드 원본

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