백준 2448 별 찍기 (11)

divide & conquer

 

#include <iostream>

#define MAX_SIZE 3072       //3*pow(2, 10)

using namespace std;


char star[MAX_SIZE][MAX_SIZE * 2];

//가장 윗 꼭짓점의 좌표(r,c), 별의 크기 n
void makeStar(int r, int c, int n) {

    //deg case
    if (n == 3) {
        //ㅁㅁ*ㅁㅁㅁ
        star[r][c] = '*';
        //ㅁ*ㅁ*ㅁㅁ
        star[r + 1][c - 1] = '*';
        star[r + 1][c + 1] = '*';
        //*****ㅁ
        star[r + 2][c - 2] = '*';
        star[r + 2][c - 1] = '*';
        star[r + 2][c] = '*';
        star[r + 2][c + 1] = '*';
        star[r + 2][c + 2] = '*';



        return;
    }

    //상, 좌하, 우하 순
    makeStar(r, c, n / 2);
    makeStar(r + n / 2, c - n / 2, n / 2);
    makeStar(r + n / 2, c + n / 2, n / 2);

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;

    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n * 2 - 1; j++) {
            star[i][j] = ' ';
        }
    }


    makeStar(0, n - 1, n);

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

    return 0;
}

 

 

주어진 예제를 보면 삼각형 3개(상, 좌하, 우하)로 나눌 수 있다.

뜯어진 삼각형도 같은 방법으로 뜯을 수 있고, 결국 
  *   

 * *  

***** 

까지 나오게 된다.

 

결국 삼각형을 저 작은 삼각형이 나올 때 까지 분할하여 처리하면 된다.