[백준/C++] 2447번: 별찍기 - 10

문제

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

---

문제 요약

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

 

ex) n = 27일 때,

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

---

코드

#include <iostream>

# define ll long long

using namespace std;

ll n;

char board[10010][10010];

// 크기가 n * n이고, 왼쪽 위 끝 점이 x, y인 별찍기
void printN(int x, int y, int n) {
    // 최소 패턴 그리기
    if (n == 3) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 1 && j == 1) continue;
                board[x + i][y + j] = '*';
            }
        }
    }

    // 8개의 작은 패턴으로 나누기
    else {
        int next_n = n / 3;

        printN(x, y, next_n);
        printN(x, y + next_n, next_n);
        printN(x, y + next_n * 2, next_n);

        printN(x + next_n, y, next_n);
        printN(x + next_n, y + next_n * 2, next_n);

        printN(x + next_n * 2, y, next_n);
        printN(x + next_n * 2, y + next_n, next_n);
        printN(x + next_n * 2, y + next_n * 2, next_n);
    }

}

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    // 모든 요소를 공백으로 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = ' ';
        }
    }
    
    // (0, 0)을 왼쪽 위 꼭짓점으로 하는 크기가 n인 패턴 그리기
    printN(0, 0, n);

    // 모양 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << board[i][j];
        }
        cout << "\n";
    }
    

    return 0;
}

---

코드 설명

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

 

크기가 n × n인 패턴 1개를 그리는 방법은 크기가 (n / 3) * (n / 3)인 패턴 8개를 그리는 방법과 같다.

 

기본 단위는 n이 3인 패턴이므로, n이 3인 순간이 오면 그때 해당하는 패턴을 2차원 배열 좌표에 찍는다.

 

+ printN(x, y, n)은 크기가 n × n이고 왼쪽 위 꼭짓점이 (x, y)인 패턴 그리기를 의미한다.