[백준] 2448번: 별 찍기 11

Solved.ac 골드4
https://www.acmicpc.net/problem/2448

설명

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

입력

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

출력

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

해결 Tip

알고리즘 분류

• 재귀

• 한 줄씩 출력하는 것 보단 배열에 전부 저장한 다음 출력
• 가장 작은 사이즈의 삼각형을 재귀함수의 최소 스텝으로 잡는다.

    *
  *   *
* * * * *

코드

#include <bits/stdc++.h>
#define MAX_SIZE 3072
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int N;  // 줄의 수
char output[MAX_SIZE+1][MAX_SIZE*2+1];

void triangle(int x, int y) {
    output[y][x] = '*';
    output[y+1][x-1] = '*';
    output[y+1][x+1] = '*';
    for (int i=-2 ; i <= 2 ; i++)
        output[y+2][x+i] = '*';
}

void solve(int k, int x, int y) {
    if (k/3 == 1) triangle(x, y);
    else {
        int nx = k / 2;
        solve(nx, x, y);
        solve(nx, x - nx, y + nx);
        solve(nx, x + nx, y + nx);
    }
}

int main() {
    fastio;
    cin >> N;
    for (int y=1 ; y <= N ; y++) {
        for (int x=1 ; x < 2*N ; x++)
            output[y][x] = ' ';
    }
    solve(N, N, 1);
    for (int y=1 ; y <= N ; y++) {
        for (int x=1 ; x <= 2*N ; x++)
            if (x == 2*N) cout << '\n';
            else cout << output[y][x];
    }
    return 0;
}