문제

별. 출력 예제의 규칙을 유추해 별을 찍는 문제다. 패턴은 시에르핀스키 삼각형 모양이다.

한 변이 2^N인 정사각형 영역을 절반 크기의 네 사분면으로 나눴을 때, 오른쪽 아래 사분면을 비우고 나머지(왼쪽 위·오른쪽 위·왼쪽 아래) 세 사분면을 같은 규칙으로 다시 채운다.

입력: 첫 줄에 N (0 ≤ N ≤ 10).

출력: 2^N 줄에 걸쳐 패턴을 출력. (각 줄은 왼쪽 정렬된 삼각형 형태)

어떤 모양이 나올까?

직접 돌려본 출력이다. N=4(한 변 16)면 이렇게 왼쪽 정렬 삼각형이 나온다.

****************
* * * * * * * *
**  **  **  **
*   *   *   *
****    ****
* *     * *
**      **
*       *
********
* * * *
**  **
*   *
****
* *
**
*

N=5로 키우면 이 삼각형이 다시 위·왼쪽·오른쪽 세 자리에 복제되는 게 보인다. 오른쪽 아래만 비니까 큰 삼각형 안에 같은 삼각형이 계속 들어앉는 시에르핀스키 모양이 된다.

********************************
* * * * * * * * * * * * * * * *
**  **  **  **  **  **  **  **
*   *   *   *   *   *   *   *
****    ****    ****    ****
* *     * *     * *     * *
**      **      **      **
*       *       *       *
********        ********
* * * *         * * * *
**  **          **  **
*   *           *   *
****            ****
* *             * *
**              **
*               *
****************
* * * * * * * *
**  **  **  **
*   *   *   *
****    ****
* *     * *
**      **
*       *
********
* * * *
**  **
*   *
****
* *
**
*

접근

이것도 정의가 곧 재귀다. 2447이 3×3 9분할이었다면, 이건 절반씩 자르는 4분할(그중 3개만 사용) 이다.

go(y, x, l) 을 “왼쪽 위가 (y, x)이고 한 변이 l인 영역을 그린다” 로 두고,

• 기저 사례: l == 0(한 칸)이면 그 칸에 별.
• 그 외: l을 절반으로 줄여 세 사분면으로 재귀한다.
  • 왼쪽 위: go(y, x, l)
  • 오른쪽 위: go(y, x + l, l)
  • 왼쪽 아래: go(y + l, x, l)
  • (오른쪽 아래는 호출하지 않음 → 그 부분이 비면서 삼각형 모양이 만들어진다)

크기는 l = 2^N 으로, 출력할 때 i번째 줄은 l - i칸까지만 찍어 왼쪽 정렬 삼각형이 되게 했다.

풀이

전체 코드: thxwelchs/algorithm

#include <iostream>
#include <vector>

using namespace std;

// 백준 16505 별
// https://www.acmicpc.net/problem/16505

int N;
char map[1025][1025];

void go(int y, int x, int l) {
    if(l == 0) {
        map[y][x] = '*';
        return;
    }

    l /= 2;

    go(y, x, l);
    go(y, x + l, l);
    go(y + l, x, l);
}


int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> N;
    // cout << N / 2;
    int l = 1; 
    for(int i=0; i<N;i++) l *= 2;
    go(0, 0, l);

    for(int i = 0; i < l; i++) {
        for(int j = 0; j < l - i; j++) {
            if(map[i][j] != '*') cout << ' ';
            else cout << '*';
        }
        cout << '\n';
    }
    return 0;
}