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

2448번: 별 찍기 - 11

재귀를 이용한 문제이다. 문제를 보면 가운데 빈칸이 있는 작은 삼각형 모형이 반복되고 있음을 알 수 있다. 이를 재귀를 통해 배열에 저장해주었다. 먼저 배열을 빈칸으로 초기화를 시켜준 다음 재귀를 돌려준다. y와 x는 가장 작은 삼각형의 가운데 위쪽 좌표를 나타내고 있다. 이를 기준으로 배열에 별을 저장해준 후 왼쪽 아래와 오른쪽 아래 삼각형을 불러오는 식으로 반복한다. 생각보다 시간이 오래걸렸다. 배열을 사용하지 않고 단순히 출력만을 이용해 문제를 해결해보려고 했는데 결국 재귀를 사용해야 겠어서 중간에 풀이 방향을 바꾸느라 시간이 좀 걸렸다.

#include <iostream>
#include <cstring>

using namespace std;

int N;
char s[3100][6200];

void star(int y, int x, int n) {
    if (n == 3) {
        s[y][x] = '*';
        s[y + 1][x - 1] = '*';
        s[y + 1][x + 1] = '*';

        for (int i = 0; i < 5; i++) {
            s[y + 2][x - 2 + i] = '*';
        }
    }
    else {
        star(y, x, n / 2);
        star(y + n / 2, x - n / 2, n / 2);
        star(y + n / 2, x + n / 2, n / 2);
    }
}

void solution() {
    memset(s, ' ', sizeof(s));

    star(0, N - 1, N);

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    solution();

    return 0;
}