[C++] BOJ 2447 / 재귀 (별 찍기10 / Divide and Conquer)

문제 분석

 

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

별 찍기 문제이지만, 규칙이 정해져 있으므로 재귀로 구현해야 한다.

 

해결 방법

N에 따라서 균등하게 9등분이 가능하다. 9등분을 하며 재귀호출을 하고, 5번 째 조각일 경우에 호출을 건너뛰면 된다.

base case는 n이 1일 때, 즉 더이상 나눌 수 없을 때 이다.

 

코드

#include <iostream>
#include <utility>
using namespace std;
char board[2188][2188];   // 3^7 == 2187
void func(int x, int y, int n) {
    if(n == 1) {
        board[x][y] = '*';
        
    }
    else {
        int div = n/3;
        for(int i=0;i<3;i++) {
            for(int j=0;j<3;j++) {
                if(i==1 && j==1) continue;
                func(x + i*div, y + j*div, div);
            }
        }
    }

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
        fill(board[i], board[i]+n, ' ');

    func(0,0,n);

    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            cout << board[i][j];
        }
        cout << "\n";
    }
}