[C++][백준 2447] 별 찍기 - 10

[문제]

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

2447번: 별 찍기 - 10

[문제 풀이]

별 찍기에서 처음으로 좌절을 느끼는 문제지만 실버 난이도의 분할 정복을 풀고 왔다면 겁먹을 것 없이 도전할 만한 문제이다.

1  2  3
4  5  6
7  8  9

로 만들어져 있는 주사위가 있다면 해당 주사위에서 5번을 제외하고 모두 별을 찍으면 된다.

그렇게 된다면 만일 크기가 9인 주사위의 경우에는

*********
* ** ** *
*********
***   ***
* *   * *
***   ***
*********
* ** ** *
*********

의 형태가 될 것이다.

즉 제일 큰 사이즈를 파악 한 뒤에 크기가 3이 되기 전까지 가운데를 제외한 1, 2, 3, 4, 6, 7, 8, 9 의 8곳으로 계속해서 분할정복을 해주면 된다.

 

만일 사이즈가 3이상이라면(10)

현재 크기의 사이즈의 1/3을 구해 1, 2, 3, 4, 6, 7, 8, 9 번으로 보내주면서 현재 사이즈를 1/3으로 줄여준다.(11~19)

현재 위치인 x, y 부터 size 를 더한값까지 5번(x+1, y+1) 을 제외하고 모두 '*'을 찍어주자. (22~29)

출력을 단순히 모두 하게 된다면 배열의 기본값인 공백은 출력이 안될 수 있기에 별표가 아닌 부분은 " "으로 출력해주자. (39~47)

[코드]

#include<iostream>
#define endl "\n"
 
using namespace std;
 
char stars[7000][7000];
 
void fold(int x, int y, int size){
 
    if(size > 3){
        fold(x,y,size/3);
        fold(x + size / 3,y, size / 3);
        fold(x + 2 * size / 3, y , size / 3);
        fold(x, y + size / 3, size / 3);
        fold(x, y + 2 * size / 3, size / 3);
        fold(x + 2 * size / 3, y + size / 3, size / 3);
        fold(x + size / 3 , y + 2 * size / 3 , size / 3);
        fold(x + 2 * size / 3, y + 2 * size / 3, size / 3);
        return;
    }
 
    for(int i = x;i< x + size;i++){
        for(int j = y;j<y + size;j++){
            if(i == x + 1 and j == y + 1){
                continue;
            }
            else{
                stars[i][j] = '*';
            }
        }
    }
    return;
}
 
int main(){
    int n;
    cin>>n;
    fold(0,0,n);
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(stars[i][j] == '*'){
                cout<<stars[i][j];
            }
            else{
                cout<<" ";
            }
        }
        cout<<endl;
    }
 
    return 0;
}