[백준/BOJ/C++] 2447번 별 찍기 10 - 분할 정복

2447번: 별 찍기 - 10

1. 문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27,...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

---

2. 입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

---

3. 출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

---

4. 풀이

입력이 27일때 예제 출력

입력이 27일때 출력된 예제를 분할 정복으로 풀기 위해서 각 구간별로 나눠보았다.

먼저 제일 처음 크게 3x3으로 나눴을때(빨간색 구분선) 정중앙 부분이 비어있고, 나누어진 각 섹션을 다시 한번 나눴을 때(파란색 구분선) 또 정중앙 부분이 비어있는 것을 볼 수 있다.

그리고 파란색 구분선으로 나누어진 나머지 부분을 보면 문제에서 주어진 패턴이 반복된다.

따라서, 주어진 입력을 3으로 나누면서 중앙부분을 비워두고 나누어진 크기가 3일 때 패턴을 반복하면 된다.

하단 코드에서 solution 함수의 else 부분이 큰 사각형을 나누는 부분이고, if(n==3) 부분이 패턴을 찍는 부분이다.

 

---

5. 소스코드

#include <iostream>
using namespace std;
bool star[6561][6561];
void solution(int x, int y, int n){
    if(n == 3){
        for(int i = x; i < x + n; i++){
            for(int j = y; j < y + n; j++){
                if(i%3 != 1 || j%3 != 1){ //문제의 패턴에서 별이 있는 부분만 true
                    star[i][j] = true;
                }
            }
        }
    }
    else{
        int k = n/3;
        for(int a = 0; a < 3; a++){
            for(int b = 0; b < 3; b++){
                if(a != 1 || b != 1){ //큰 사각형에서 가운데를 비운다.
                    solution(x+a*k, y+b*k, k);
                }
            }
        }
    }
}
int main(){
    int N;
    cin>>N;
    solution(0, 0, N);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(star[i][j]){
                cout<<"*";
            }
            else{
                cout<<" ";
            }
        }
        cout<<"\n";
    }
    return 0;
}