[재귀 / BOJ 2447 / C++] 별찍기 - 10

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

2447번: 별 찍기 - 10

이것 역시 앞의 문제들과 유사하게 풀면된다. 반복되는 모양을 캐치해서 이를 어떻게 구현할지가 키포인트 같다!

나는 단순하게 2차원 배열을 통해 모양이 시작되는 각 좌표를 재귀함수가 호출될때마다 넘겨주었다.

 

N = 27

N=9

N=3

위의 패턴들의 느낌을 봐보자. 사각형을 9개의 사각형으로 나눠야할 거 같지 않은가?

근데 또 각각의 사각형은 또 9개의 사각형을 나눠지고 ... 이게 계속해서 반복된다.

 

따라서 이 느낌 그대로 재귀함수 내에서 함수를 다시 8번 호출해줬다! (8번인 이유는 9개의 사각형 중 가운데 뻥 뚫려 있는 부분이 다르기 때문이다. 이 부분은 따로 표현해줘야한다.)

또한 최종적인 Base Condtion은 N=3 일때의 모양을 출력해주면 될 것이다.

 

 

1) '*'로 채워진 NxN 2차원 배열을 만든다.
2) N==3일 경우, 가운데만 구멍이 뚫려  있는 사각형을 만든다.
((시작 x좌표 + 1, 시작 y좌표 + 1) 을 ' ' 으로 바꿔주면됨) 
3) N>3인 경우, 사각형을 9등분하여 각각의 사각형의 시작 좌표를 함수에 다시 넣어준다. 단, 가운데 뚫려있는 사각형은 별도로 표현해준다.
4) 완성된 NxN 2차원 배열을 출력한다. 

별찍기 - 11 도 같은 원리로 풀 수 있다. 별찍기 - 10 을 풀었다면 별찍기 - 11도 풀어보자!

#include <bits/stdc++.h>

using namespace std;

int N;
int stars[2300][2300]; // 모두 0으로 초기화 됐다.

void func(int n, int x, int y){
    if(n==3) {stars[x+1][y+1] = 1; return;} // stars[x+1][y+1] = 1이면, (x+1, y+1) 좌표는 공백을 출력함.

    int k = n/3;
    func(k, x, y);
    func(k, x+k, y);
    func(k, x+2*k, y); // 첫째줄

    func(k, x, y+k);
    for(int i = x+k ; i < x+2*k; i++){
        for(int j = y+k; j < y+2*k; j++){
            stars[i][j] = 1;
        }
    }  // 9개의 사각형 중 가운데 비어있는 사각형을 따로 구분해서 만들어줌.
    func(k, x+2*k, y+k); // 둘째줄

    func(k, x, y+2*k);
    func(k, x+k, y+2*k);
    func(k, x+2*k,  y+2*k); // 셋째줄

}

int main(void){
    ios::sync_with_stdio(0);
    cin >> N;

    func(N, 0, 0);

    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            if(stars[i][j]) cout << " "; // '1' 인 부분은 공백을, '0' 인 부분은 별로 출력함.
            else cout << "*";
        }
        cout << '\n';
    } // '*' 만 있는 배열에 ' '으로 구멍을 뚫어준다는 느낌으로 풀면됨.
}