2448번: 별찍기 - 11

https://www.acmicpc.net/problem/2448

$O(n^2)$

가장 작은 삼각형이 그려지는 모양을 보면
파스칼의 삼각형을 이루는 숫자들 중 홀수만 칠한 것과 같음을 알 수 있다.

#include<cstdio>
int n, a[3072][6146];
int main() {
    scanf("%d", &n);
    a[0][n - 1] = a[1][n - 2] = a[1][n] = a[2][n - 3] = a[2][n - 2] = a[2][n - 1] = a[2][n] = a[2][n + 1] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2 * n - 1; j++) {
            if (i > 2) a[i][j] = (j>2 && a[i - 3][j - 3]) ^ a[i - 3][j + 3];
            putchar(" *"[a[i][j]]);
        }
        puts("");
    }
    return 0;
}