별 찍기 - 11

13 May 2022 in Algorithm on 재귀, 분할정복

solved_ac[Class4] 별 찍기 -11

문제

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

입력

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

출력

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

예제 입력 1

24

예제 출력 1

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

알고리즘 분류

[재귀], [분할 정복]

문제에 대한 접근

재귀의 규칙은 어렵지 않게 찾을 수 있었다. 그러나 “공백을 어떻게 처리할 것인가?”에 대하여 오랜 고민의 시간을 보냈다. 처음에 print로 접근하여서 공백처리하는데 꽤 애를 먹었다. 결국, matrix를 활용하면 공백처리가 가능하겠구나 깨닫고 이를 바탕으로 코드 작성을 하였다.

1트

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# 초기 조건
n = int(input())
plane = [[" " for _ in range(2*n-1)] for _ in range(n)]

def print_star(x,y,n):
    # Base Case
    if n == 3:
        plane[x][y] = "*"
        plane[x-1][y+1] = "*"
        for i in range(-2,3):
            plane[x+i][y+2] = "*"
    
    else:
        print_star(x,y,n//2)
        print_star(x-n//2,y+n//2,n//2)
        print_star(x+n//2,y+n//2,n//2)

print_star(0,n-1,n)

for i in plane:
    print("".join(i))

처음에 x축 y축을 잘못 잡아서 틀렸다. 수학에서의 그래프에 익숙해서 습관적으로 x,y축을 거꾸로 잡았는데 matrix에서는 행이 우선이므로 그래프를 다음과 같이 잡아야한다.

또한 Base Case 부분의 코드에서 빠뜨린 부분이 있어 추가하여 2트에 올바른 결과가 나왔다.

2트

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# 초기 조건
n = int(input())
plane = [[" " for _ in range(2*n-1)] for _ in range(n)]

def print_star(x,y,n):
    # Base Case
    if n == 3:
        plane[x][y] = "*"
        plane[x+1][y-1] = "*"
        plane[x+1][y+1] = "*"
        for i in range(-2,3):
            plane[x+2][y+i] = "*"
    # General Case
    else:
        print_star(x,y,n//2)
        print_star(x+n//2,y-n//2,n//2)
        print_star(x+n//2,y+n//2,n//2)

print_star(0,n-1,n)

for i in plane:
    print("".join(i))