백준 2448번 별 찍기 - 11

정보

문제 바로가기 [클릭]

난이도: Gold4

관련 개념: #재귀

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

24

출력

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

---

코드(파이썬)

import sys


def pattern(num, i, j):
    if num == 3:
        for x, y in tri:
            result[x+i][y+j] = "*"
    else:
        pattern(num//2, i, j+num//2)
        pattern(num//2, i+num//2, j)
        pattern(num//2, i+num//2, j+num)

n = int(input())

result = [[" "] * (n//3 * 5 + n//3 - 1) for _ in range(n)]
tri = ((0,2), (1,1), (1,3), (2,0), (2,1), (2,2), (2,3), (2,4))
pattern(n, 0, 0)

sys.stdout.write("\n".join(["".join(row) for row in result]))

---

특이사항

• 재귀 문제였지만 생각보다 많은 메모리와 시간 소모에 아쉬움을 느낌
• 내 코드(211,408KB, 700ms)에 비해 우수한 코드(바로가기, 71,624KB, 128ms)와 비교

  • import sys
    
    
    def solution(N):
        if N == 3:
            return ["  *  ", " * * ", "*****"]
    
        nn = N // 2
        star = []
        sub = solution(nn)
        for i in range(nn):
            star.append(f'{" " * nn}{sub[i]}{" " * nn}')
        for i in range(nn):
            star.append(f'{sub[i]} {sub[i]}')
        return star
    
    
    IN = int(sys.stdin.readline())
    print("\n".join(solution(IN)))
    

  • 재귀 함수
    • 기존: 2차원 리스트 생성 이후 각 요소마다 * 문자로 변경
    • 개선: star 리스트에 각 줄을 저장하고 반환

---

참고문헌

-