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

분류: 재귀 /

 

문제

문제 링크

문제 설명

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N이 주어진다. N은 항상 3×2^k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

풀이

#include <iostream>
using namespace std;

int N;
bool board[3072][6144];

void fillStar(int x, int y, int n) {
    if(n == 3) {
        board[x-2][y+2] = true;
        board[x-1][y+1] = board[x-1][y+3] = true;
        for(int i=0; i<5; i++) board[x][y+i] = true;
        return;
    }
    fillStar(x - n/2, y + n/2, n/2);
    fillStar(x, y, n/2);
    fillStar(x, y + n, n/2);
}
void printStar() {
    for(int i=0; i<N; i++) {
        for(int j=0; j<2*N; j++)
            cout << (board[i][j] ? '*' : ' ');
        cout << '\n';
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    fillStar(N-1, 0, N);
    printStar();
}

2학년에 수강했던 컴퓨터그래픽스 수업에서 OpenGL로 프랙탈 삼각형을 그렸던게 생각났다.

좌하단을 기준으로 삼각형을 재귀적으로 그린다.

`N`은 전체 높이이며 삼각형 사이에 한칸 빈칸을 포함하여 가로의 길이는 `2N`이다.

높이가 `n`인 현재 삼각형의 좌하단 좌표를 `(x, y)`라 하면 한 단계 아래 삼각형의 좌하단의 좌표는 `(x, y)`, `(x, y+n)`, `(x - n/2, y + n/2)`이고 높이는 `n/2`이다.