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

[문제]

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

2448번: 별 찍기 - 11

[문제 풀이]

분할정복을 이용해서 풀자.

별 찍기 - 10 과 비슷하게 풀 수가 있으나 처음 위치를 x좌표를 n-1로 두어야 하는 것에 유의하자.

 

만일 사이즈(높이)가 3보다 크다면(10)

위치를 3곳으로 나누어 주자.

첫번째 위치는 현재 위치 그대로(11)

두번째 위치는 x를 현재 크기의 1/2를 뺀 지점, y를 현재 크기의 1/2를 더한 지점으로 (12)

세번째 위치는 x를 현재 크기의 1/2를 더하고 y를 현재 크기의 1/2를 더한 지점으로 보내자.(13)

 

현재 크기가 3이라면 별을 현재 위치, 현재위치에서 높이가 1내려간(배열로는 올라간) 위치에서 양옆에 찍어주자.(17~19)

마지막으로 받침에 x좌표가 현재 위치의 -2인 지점부터 시작해서 5칸 별을 찍어주자.(21~22)

 

x의 크기는 0부터 2*n-1까지 이니 범위에 주의하자.(35)

[코드]

#include<iostream>
#define endl "\n"
 
using namespace std;
 
char star[10000][10000];
 
void fold(int y, int x, int size){
 
    if(size > 3){
        fold(y ,x ,size/2 );
        fold(y + size / 2 ,x - size / 2 ,size/2);
        fold(y + size / 2, x + size / 2  ,size/2);
        return;
    }
 
    star[y][x] = '*';
    star[y+1][x-1] = '*';
    star[y+1][x+1] = '*';
 
    for(int i = x;i<x+ size * 2 -1; i++){
        star[y+2][i-2] = '*';
    }
 
    return;
}
 
int main(){
    int n;
    cin>>n;
 
    fold(0,n-1,n);
 
    for(int i = 0;i<n;i++){
        for(int j = 0 ;j< n * 2-1 ;j++){
            if(star[i][j] == '*'){
                cout<<'*';
            }
            else{
                cout<<" ";
            }
        }
        cout<<endl;
    }
 
 
    return 0;
}