[백준 2447] 별 찍기 - 10

 재귀가 익숙하지 않으면 풀기 힘든 문제다. 근데 알고보면 별 거 없다.

 \(n = 3\)의 별 모양을 보자

가운데 별 하나가 빠진 모양이다.

 

 \(n = 9\)인 것을 보자

가운데 \(n = 3\)의 별 모양 하나가 빠진 모양이다.

 

\(n = 27\)인 것을 보자.

 가운데 \(n = 9\)의 별 모양 하나가 빠진 모양이다.

 

 끝났다. \(n = 3^k\)의 별 모양은 \(n = 3^{k - 1}\) 별 모양 하나가 가운데에 비어있는 모양이다.

 \(n = 3^k\)부터 \(n = 1\)까지 재귀적으로 별 모양을 그리면 원하는 별 모양을 얻을 수 있다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

char star[2201][2201] = { 0 , };

void recur(int x, int y, int cur)
{
	// n = 1이면 별 찍고 리턴
    if (cur == 1)
    {
        star[x][y] = '*';
        return;
    }
    
    int next = cur / 3;
	
    // 가운데 빼고 재귀로 돌기
    // 1 2 3
    // 4   6
    // 7 8 9
    // 항상 이렇게 이중 for문이 돈다.
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == 1 && j == 1) // 가운데는 스킵
                continue;
            else
                recur(x + (i * next), y + (j * next), next);
        }
    }		
}
int main()
{
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    // 모두 빈칸으로 초기화
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) star[i][j] = ' ';

    // 재귀 시작
    recur(0, 0, n);
	
    // 출력
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << star[i][j];
        }
        cout << '\n';
    }
	
    return 0;
}