2448번: 별 찍기 - 11

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

2448번: 별 찍기 - 11

프랙탈이란 일부분이 전체와 같은 모양을 가진 도형을 말한다.

삼각형의 가운데가 비어있고, 주변 세 삼각형의 가운데 또한 비어있고, 이 구조가 반복된다

예제를 아홉개의 사각형으로 나누면, 한가운데의 삼각형이 비어있고, 주변 세 삼각형 역시 가운데가 비어있으며, 그 구조가 각 삼각형에 대해서 반복되므로 프랙탈이라 볼 수 있다.

이 문제를 풀기 위해선 우선 가장 기본이 되는 N = 3 형태를 지정해준 뒤, N이 입력받은 값이 될 때까지 이전 형태를 복사해 저장하는 것으로 현재 형태를 만들면 된다.

#include <cstdio>

#define MAX_N 3 * 1024

// 계산의 편의를 위해 삼각형을 뒤집어서 저장
bool ans[MAX_N][2 * MAX_N] = {{ 1, 1, 1, 1, 1, 0 },
                              { 0, 1, 0, 1, 0, 0 },
                              { 0, 0, 1, 0, 0, 0 }};

int main() {
    // 삼각형의 높이
    int N;

    // 높이를 입력받은 뒤
    scanf("%d", &N);
    // 프랙탈의 크기가 주어진 크기가 될 때까지 프랙탈화 반복
    for (int n = 3; n < N; n *= 2)
        // 삼각형의 오른쪽과 위쪽 꼭지점에 기존 삼각형을 복제해 프랙탈 생성
        for (int i = 0; i < n; i++) for (int j = 0; j < 2 * n; j++)
            ans[i + n][j + n] = ans[i][j + 2 * n] = ans[i][j];

    // 삼각형을 밑변부터 차례로 출력
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < N * 2; j++) printf("%c", ans[i][j] ? '*' : ' ');
        printf("\n");
    }

    return 0;
}