2447번

2447번 - 별찍기 10

규칙을 찾아서 해결하는 문제.

문제의 조건에서 3의 k 제곱으로 주어진다고 했으므로 뭔가 3이나 9와 연관이 있는 규칙이 있을거라 추측이 가능했다.

그래서 보니 9개로 나누었을 때, 재귀적으로 반복되는 것이 보였다.

따라서 분할정복의 방식으로  분할하고 재귀로 푸는 방법으로 접근했다.

* 풀면서 발생했던 문제

- 나는 별을 재귀함수 내에서 곧바로 출력하는 방식으로 문제를 풀려고 했었다. 내가 다른 별찍기 문제를 풀었던 것처럼...

근데 그러다보니 분할 정복인데, 분할 정복이기 때문에 같은 줄에 1사분면과 2사분면을 배치하는 것이 불가능했다...

이를 굉장히 오랜시간 뒤에 깨달았다.. 물론 푸는 도중에 배열을 사용해서 할까 하다가도 스스로의 고집 때문에 계속 같은 방식을 고수했다..

이는 분명 고쳐야할 문제점인 것 같다. 배열을 써서 푸니까 너무나 간단한 문제가 되어 버렸다..

사각형을 9분할 하고 , 가운데 인 경우 i==1 && j==1 인 경우만 출력을 안하도록 코딩하였다.

<정답 코드>

#include<iostream>
using namespace std;
int N;
bool map[6562][6562];
 
void makeMap(int x, int y, int n)
{
    if (n == 1)
    {
        map[x][y] = true;
        return;
    }
 
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            int nn = n / 3;
            int nx = x + nn*i;
            int ny = y + nn*j;
            if (i != 1 || j != 1)
            {
                makeMap(nx,ny,nn);
            }
        }
    }
 
    return;
}
int main()
{
    cin >> N;
 
    makeMap(0, 0, N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j])
            {
                cout << "*";
            }
            else
            {
                cout << " ";
            }
        }
 
        cout << endl;
    }
 
    return 0;
}