[BOJ 2447] 별찍기 - 10

문제 출저 : https://www.acmicpc.net/problem/2447

 

풀이 : 

 

분할 정복 문제입니다.

출력을 자세히 보면 

***

* *

***

위 의 모양 처럼 중간 부분만 뻥 뚤린 형태를 유지하고 있음을 유추할 수 있습니다.

따라서 중간 부분만 출력 하지 않도록 9가지 구역으로 분할 후 정복하시면 됩니다.

 

#include<stdio.h>
 
int n;
char arr[7000][7000];
 
void divide(int y,int x,int size,int cnt)
{
    if (size == 1||cnt==4)
    {
        arr[y][x] = cnt==4 ? ' ':'*';
        return;
    }
    size /= 3;
    cnt = 0;
    for (int i = 0, j = x; i < 3; i++, cnt++, j += size)divide(y, j, size, cnt);
    for (int i = 0, j = x; i < 3; i++, cnt++, j += size)divide(y+size, j, size, cnt);
    for (int i = 0, j = x; i < 3; i++, cnt++, j += size)divide(y+size*2, j, size, cnt);
}
 
int main()
{
    scanf("%d", &n);
    divide(0, 0, n, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if(arr[i][j]=='*')printf("%c", arr[i][j]);
            else printf(" ");
        }
        printf("\n");
    }
}