[BOJ] 별 찍기 - 10

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

2447번: 별 찍기 - 10

문제에는 아래 그림과 같은 출력 결과를 주고 규칙을 찾아서 별을 찍으라고 나와있다. N은 항상 3의 제곱 꼴인 수라는 게 힌트다.

아래 그림은 N이 27인 경우인데 27인 경우 27*27 모양이고 빈칸이 비어 있는 모양인 것을 볼 수 있다.

 

 

N이 9였다면 아래 그림과 같이 9*9 크기의 빨간 네모 부분이 출력됐을 거다. 여기서도 마찬가지로 가운데 부분이 비어있다는 것을 알 수 있다. N이 3인 경우에도 왼쪽 맨 위쪽 끝부터 3*3크기를 보면 가운데 비어있는 모양인 것을 볼 수 있다.

결국 이 문제는 처음에 27을 입력받았다면 3으로 나눠서 각각 9*9로 이루어진 9칸을 다시 9칸을 모두 각각 3으로 나눠서 3*3인 칸에 대해서 별을 찍으면 된다. 즉 재귀를 이용하여 분할 정복(Divide and Conquer)으로 풀 수 있다.

 

 

n이 1이 될때까지 계속 3으로 나눠서 재귀 호출을 한다. 호출에서 재귀 호출은 총 8번 일어난다.

가운데 빈칸을 제외하고 총 위쪽 3개, 아래쪽 3개, 가운데 2개를 별을 찍어줘야하기 때문이다.

별은 n이 1이 될때까지 분할한 후에 찍어준다.

 

 

예를 들어 n이 9인 경우 아래 그림에서 빨간 네모 부분과 같은 3*3 만큼씩 각각 8번 호출하게 된다. (가운데 부분은 호출하지 않기 때문)

처음에 (0,0)에서 시작했다면 그다음은 (0,3)에서 시작하고 그다음은 (0,6)에서 호출한다.

다시 그다음은 중간 시작점인 (3,0)이고 그다음 (3,3)은 가운데 이므로 호출하지 않고 넘어간다. 이런 식으로 재귀 호출을 진행하면

각 호출에서는 다시 3*3 에 대해서 다시 8번 호출을 하여 1*1이 되어서 별을 찍게 된다.

 

 

 

(배열의 크기는 문제에서 주어진 최대 값이 3의 8 제곱보다 큰 수 2200으로 잡았다)

#include <iostream>
using namespace std;
 
char map[2200][2200];
 
void solve(int x, int y, int n) {
 
    if (n == 1) {
        map[x][y] = '*';
        return;
    }
 
    int div = n / 3;
    
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            //가운데인 경우 별을 찍지 않는다.
            if (i == 1 && j == 1) continue;
 
            solve(x+ (div * i), y+(div * j), div);
        }
    }
 
}
 
int main() {
 
    int n;
    cin >> n;
 
 
    //먼저 공백으로 채워준다.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = ' ';
        }
    }
 
    
    solve(0, 0, n);
 
 
    //출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << map[i][j];
        }
        cout << '\n';
    }
 
 
    return 0;
}