문제

별 찍기 - 10. 재귀적인 별 패턴을 출력하는 문제다.

크기 N의 패턴은 N×N 정사각형이다.

• 크기 3의 패턴(기본): 가운데 한 칸만 공백이고 나머지 8칸은 별.
• 크기 N(N>3)의 패턴: 전체를 3×3으로 나눈 9개 블록 중 가운데 블록은 공백, 나머지 8개 블록은 각각 크기 N/3의 패턴으로 채운다.

입력: 첫 줄에 N. N은 3의 거듭제곱으로 N = 3^k, 1 ≤ k < 8 (즉 N은 3 ~ 2187).

출력: 첫 줄부터 N번째 줄까지 패턴을 출력.

어떤 모양이 나올까?

말로는 감이 안 와서, 직접 돌려본 출력을 옮겨왔다. N=9면 이렇게 나온다.

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

N=27이 되면 위의 9칸짜리 패턴이 다시 가운데를 비운 3×3으로 배치된다. 자기 자신을 닮은(self-similar) 구조가 눈에 보인다.

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

접근

정의 자체가 재귀다. “크기 N 패턴 = 가운데를 비운 크기 N/3 패턴 8개”라는 문장이 그대로 분할 정복이 된다.

print_star(r, c, n) 을 “왼쪽 위가 (r, c)이고 한 변이 n인 정사각형 영역을 그린다” 로 정의했다.

• 기저 사례: n == 1이면 그 칸 하나에 별을 찍고 끝.
• 그 외: 영역을 3×3 블록(각 블록 크기 n/3)으로 나눠, 가운데(i==1, j==1)만 건너뛰고 나머지 8개 블록의 시작 좌표 (r + i·n/3, c + j·n/3)로 재귀 호출.

별을 바로 출력하지 않고 2차원 배열 stars에 먼저 채운 뒤, 마지막에 한 번에 출력했다. 채워지지 않은 칸('\0')은 공백으로 찍으면 된다.

풀이

전체 코드: thxwelchs/algorithm

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 백준 2447 별 찍기 10
// https://www.acmicpc.net/problem/2447

const int MAX = 2187; // 3^7 까지 가능

int N;
char stars[MAX + 1][MAX + 1];

void print_star(int r, int c, int n) {

    if(n == 1) {
        stars[r][c] = '*';
        return;
    }

    n /= 3;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            if(i == 1 && j == 1) continue;
            print_star(r + i * n, c + j * n, n);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;

    print_star(0, 0, N);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(stars[i][j] == '\0') cout << ' ';
            else cout << stars[i][j];
        }
        cout << "\n";
    }
    
    return 0;
}