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

문제링크 : https://www.acmicpc.net/problem/2448

2448번: 별 찍기 - 11

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

char arr[3072][6143]; //세로 N, 가로 2N-1

void draw(int y, int x, int n) 
{
    if(n==3) //반복되는 기본 형태 그리기
    {
        arr[y][x] = '*'; //첫째줄
        arr[y+1][x-1] = '*'; //둘째줄
        arr[y+1][x+1] = '*'; //둘째줄
        for(int i=0; i<5; i++) //셋쨰줄
        {
            arr[y+2][x-2+i]='*';
        }
        return;
    }
    draw(y, x, n/2); //맨 위
    draw(y + n/2, x - n/2, n/2); //왼쪽
    draw(y + n/2, x + n/2, n/2); //오른쪽
}
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    cin >> N;

    draw(0, N-1, N);

    for(int i=0; i<N; i++) 
    {
        for(int j=0; j<2*N-1; j++)
        {
            cout << (!arr[i][j] ? ' ' : arr[i][j]);
        }
        cout <<"\n";
    }
    
    return 0;
}

먼저 반복되는 기본 삼각형 형태를 일일히 찍어준다.

이후 보면 가로 길이가 계속 2배가 되면서 삼각형이 반복되는 것을 볼 수 있다.

 

가장 위에 있는 삼각형이 원래 기본 좌표 (y, x)의 삼각형이다.

이때 기본 N에서 재귀를 통해 2를 나누면서 반복하기에 N은 N/2가 된다.

 

왼쪽 삼각형은 X로 N/2만큼이 감소, Y로 N/2만큼이 증가된 위치의 삼각형이다.

오른쪽 삼각형은 X로 N/2만큼이 증가, Y로 N/2만큼이 증가된 위치의 삼각형이다.

 

위 3가지를 이용하여 재귀를 반복하고, 기본 형태가 출력되는 조건인 N이 3일 때 기본 삼각형을 출력하도록 해주면 된다.

 

여기서 공백부분은 나중에 출력할때 한꺼번에 처리해도 되지만 속도가 상당히 느려진다.

N을 입력받고 먼저 공백으로 초기화해주고 시작하면 나중에 공백과 같이 출력하는 것보다 속도는 상당히 빨라진다.

 

하지만 나는 코드가 짧은게 보기 편해서 출력을 모두 같이 처리했다.