별 찍기 11 (boj 2448)

별 찍기11 문제는 분할정복(Divide and conquer) 기법으로 문제를 해결할 수 있습니다.

삼각형 안에 작은 삼각형이 들어있는 꼴이기 때문입니다.

 

코드

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>

#define INF 987654321

int N;
char arr[5000][10000];

void drawTri(int y, int x) {
    sprintf(arr[y - 2] + x, "  *  ");
    sprintf(arr[y - 1] + x, " * * ");
    sprintf(arr[y] + x, "*****");
}

void draw(int y, int x, int size) {
    if (size == 0) {
        drawTri(y, x);
        return;
    }

    int width = pow(2, size - 1) * 6;
    draw(y, x, size - 1);
    draw(y, x + width, size - 1);
    draw(y - width / 2, x + width / 2, size - 1);
}

int main() {
    scanf("%d", &N);

    int size = log2(N / 3);
    draw(N, 0, size);

    for (int y = 1; y <= N; y++) {
        for (int x = 0; x < 2 * N; x++) {
            if (arr[y][x] == '\0')
                putchar(' ');
            else
                putchar(arr[y][x]);
        }
        putchar('\n');
    }
    return 0;
}