[BOJ][🟡4][백준#02448] 별 찍기 - 11

문제 출처

BAEKJOON Online Judge #2448

문제

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

입력

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

출력

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

예제

입력

24

출력

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

My Sol

def foo(ni, nj, M):
    if M == 3:
        k = 0
        while k < 3:
            for j in range(-k, k+1):
                mat[ni+k][nj+j] = '*'
            k += 1
        mat[ni+1][nj]=' '
        return

    H = M//2
    foo(ni, nj, H)
    foo(ni+H, nj-H, H)
    foo(ni+H, nj+H, H)


N = int(input())
mat = [[' ']*(2*N-1) for _ in range(N)]
foo(0, N-1, N)

for lst in mat:
    print(*lst, sep='')

각 삼각형의 맨 위의 좌표를 기준점으로 두고, 트리 형식으로 나뉘어 범위가 1/2배씩 작아질 때마다 3개의 기준점으로 갈라지는 방식을 사용하였다. 이후, 전달해준 크기가 3이 되면, 가장 작은 단위의 삼각형이 되므로, 이를 좌표에 표시해준 뒤, return하며 가장 작은 삼각형에 대한 작업들의 집합으로 풀어주면 되겠다.

결과

맞았습니다!!

모범답안

출처

import math
def makeStar(n):
  
  star.append(['  *  ',' * * ','*****'])
  
  for k in range(1,n+1):
    listT = list()
    
    for i in range(len(star[k-1])):
      listT.append(' '*3*2**(k-1) + star[k-1][i] + ' '*3*2**(k-1))
    for i in range(len(star[k-1])):
      listT.append(star[k-1][i] + ' ' + star[k-1][i])

    star.append(listT)
  
star = list()

n = int(input())
n = int(math.log2(n//3))

makeStar(n)

for i in range(len(star[n])):
  print(star[n][i])

연산시간이 정말 빠른 풀이가 있어 분석해보려 한다. DP를 이용한 것처럼 보이고, 가장 작은 단위 삼각형을 배열 star의 0번 인덱스에 저장하였다. 이후 규칙성에 맞게 수적으로 공백과 star 배열 내의 별의 크기를 listT에 저장하여 star의 새로운 인덱스에 추가하였다. 즉, 인덱스가 커질 때마다 이전 인덱스의 삼각형을 단위로 하여 3개를 모아 큰 삼각형을 만드는 배열을 계산하는 것이다.

이후 입력값을 3으로 나눈 값의 log2를 취해 구해 반복횟수를 결정해주고, star 배열의 맨 마지막 인덱스의 삼각형을 출력해주면 된다.