[백준/C++] 2448번: 별찍기 - 11

문제

https://www.acmicpc.net/problem/2448

2448번: 별 찍기 - 11

---

문제 요약

예제를 보고 규칙을 유추하여 별을 출력한다.

 

ex) n = 24일 때

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

 

---

코드

#include <iostream>
#include <cstring>
#include<algorithm>
using namespace std;

char star[3072][6144];

// 위쪽 꼭짓점 좌표가 (x, y)이고, 높이가 N인 삼각형 그리기
void fillStar(int x, int y, int n) {

    // 기본 삼각형 그리기
    if (n == 3) {
        // 3층
        star[x][y] = '*';

        // 2층
        star[x + 1][y - 1] = '*';
        star[x + 1][y + 1] = '*';

        // 1층
        star[x + 2][y - 2] = '*';
        star[x + 2][y - 1] = '*';
        star[x + 2][y] = '*';
        star[x + 2][y + 1] = '*';
        star[x + 2][y + 2] = '*';
    }

    else {
        fillStar(x, y, n / 2); // 위쪽 작은 삼각형
        fillStar(x + n / 2, y - n / 2, n / 2); // 왼쪽 아래 작은 삼각형
        fillStar(x + n / 2, y + n / 2, n / 2); // 오른쪽 아래 작은 삼각형
    }
}

// 별 출력
void printStar(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2 * n - 1; j++) {
            cout << star[i][j];
        }
        cout << "\n";
    }
}

int N;

int main() {
    cin >> N;

    memset(star, ' ', sizeof(star)); // 빈칸으로 초기화
    
    fillStar(0, N - 1, N);

    printStar(N);

    return 0;
}

---

코드 설명

재귀를 이용한 분할 정복 기법을 이용한다.

 

즉, 높이가 n인 삼각형 한 개를 그리는 방법은 높이가 n / 2인 삼각형 3개를 그리는 방법과 같다.

 

기본 단위는 높이가 3인 삼각형이므로, n이 3인 순간이 오면 그때 해당하는 삼각형(이차원 배열 star)의 좌표에 '*'을 찍는다.

 

재귀 함수 fillStar의 인자 x, y, n는 높이가 n인 삼각형의 위쪽 꼭짓점 좌표이다.