본문 바로가기
알고리즘 PS (백준)/🐍 Python (파이썬)

[백준 2448] 별 찍기 - 11 (파이썬 Python)

by 코딩하는 동현😎 2023. 9. 25.

별 찍기 - 11

 

문제

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

입력

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

출력

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


예제 입력

24

예제 출력

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

규칙 찾기

나와있는 별찍기 모양을 보시면 아래와 같은 규칙이 있습니다.

 

 

아래를 이전 그래프라고 하겠습니다.

n = 6일때 그래프인데, 높이는 n , 가로 길이는 2*n-1 = 11 인것을 확인할 수 있습니다.


그 이전 그래프를 양옆으로 복제를 하면


아래와 같이 다음 그래프가 나옵니다.

다음 그래프는 기존의 그래프의 n을 두배한 12 그래프입니다. (new n = 12)

가로 길이는 2*n-1해서 23이고,

두 그래프를 복제할때는 시작할 인덱스는 (가로길이-이전가로길이)/2 한걸 알수 있습니다. 

그러면 여기서 또 다음 그래프를 구하려면 이 그래프를 가지고 똑같은 과정을 재귀적으로 반복하면 계속 다음다음 그래프를 구할 수 있습니다.


파이썬 코드

위 방법을 그대로 파이썬 코드로 옮긴 결과입니다.

설명은 주석에 있습니다.

N = int(input())

# 길이가 3인 초기 그래프
graph = [[" ", " ", "*", " ", " "], [" ", "*"," ", "*", " "], ["*", "*", "*", "*", "*"]]

# 길이가 3인 초기 그래프를 받아서 3*2 = 6을 호출한다
# 6에서는 길이가 3인 그래프를 좌우로 복제시켜서 6인그래프를 만들고
# 길이가 6인그래프를 넘겨줘서 다음 길이가 6*2=12인 그래프를 6인그래프 두개를 복제해서 만들도록 한다
def makeTri(n, before):
    if n == N:
        return before
    # 이전 그래프의 가로 길이
    length = 2*n-1
    # 새 그래프의 가로길이
    newLength = 2*2*n-1
    after = [[" "]*(newLength) for _ in range(2*n)]
    # 기존 그래프 1차적으로 복사할때 시작할 인덱스
    startIdx = (newLength-length)//2
    # 기존 그래프 1차적으로 복사
    for i in range(n):
        after[i][startIdx:startIdx+length] = before[i]

    # 기존 그래프를 양옆에 하나씩 복사
    for i in range(n):
        after[n+i] = before[i] + [" "] + before[i]
    # 다음 그래프 재귀 호출 (n이 N과 같아질때까지 반복)
    return makeTri(n*2, after)

# 3부터 시작해서 N될때까지 재귀
graph = makeTri(3, graph)

#그래프 출력
for i in range(N):
    print(''.join(graph[i]))
반응형

댓글