이번 문제는 분할 정복으로 해결하였다. 전에 풀어보았던 별 찍기보다 복잡한 형태의 문제여서 고민을 많이 했다. 출력되는 별이 많으므로 2차원 배열에 저장하기로 하였다.

• n의 범위가 3x2^10까지이므로 3072까지 가능하다. 예제 출력을 자세히 보면 가장 위에 별이 가로축에서 n번째에 위치하는 것을 알 수 있으므로 MAX를 (3027+1)*2로 정의해준다. 별을 담는 star배열은 star[MAX/2][MAX]가 된다.
• 재귀함수를 통하여 분할 정복을 해준다.
• 이때 높이에 해당하는 h가 이라면 작은 삼각형을 이루는 별을 배열에 삽입해준다.
• 그 외의 경우에는 각각 현재 위치에서 위, 좌, 우 방향으로 삼각형을 생성해줘야 하므로 h의 절반 값인 nh를 높이로 하여 재귀함수를 호출한다. nh는 재귀함수마다 절반으로 줄어 3이 될때까지 쪼개지고 3이 되면 별을 삽입하게 된다.

Code

#include <iostream>
#define MAX 2*(3072+1)
using namespace std;

int n;
char star[MAX/2][MAX];

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

void Solution(int h, int y, int x){
    if(h==3){
        star[y][x]='*';
        star[y+1][x-1]='*';
        star[y+1][x+1]='*';
        for(int i=x-2; i<x+3; i++){
            star[y+2][i]='*';
        }
        return;
    }
    else{
        int nh=h/2;
        Solution(nh, y, x);
        Solution(nh, y+nh, x-nh);
        Solution(nh, y+nh, x+nh);
    }
}

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution(n, 0, n-1);
    Solve();
    return 0;
}