10993번: 별 찍기 - 18

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


$O(4^n)$

#include<cstdio>
int c[1023][2045], n, l, r, x;
int main() {
    scanf("%d", &n);
    r = (1 << n + 1) - 4;
    if (n & 1) x = (1 << n) - 2;
    for (int i = n; i >= 1; i--) {
        int j = 0;
        for (; j < (1 << i) - 1; j++) {
            i & 1 ? c[x - j][l + j] = c[x - j][r - j] = 1 : c[x + j][l + j] = c[x + j][r - j] = 1;
            c[x][l + j] = c[x][r - j] = 1;
        }
        i & 1 ? x -= j / 2 : x += j / 2;
        l += j / 2 + 1;
        r -= j / 2 + 1;
    }
    for (int i = 0; i < (1 << n) - 1; i++) {
        int e = 0;
        for (int j = 0; j < (1 << n + 1) - 3; j++) if (c[i][j]) e = j;
        for (int j = 0; j <= e; j++) putchar(" *"[c[i][j]]);
        puts("");
    }
    return 0;
}