[백준][2447번] 별 찍기 - 10 [cpp, c++]

백준 2447 장군

• 재귀(recursion)와 분할 정복(divide and conquer)을 이용해야 되는 문제이다.
• 오랜만에 문제를 풀다보니 상당히 애를 먹었던 문제였다 ㅠㅠ
• www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

풀이 방법

1) 3*3 가운데가 뚫린 사각형이 존재하는 사각형이 반복되는 형태이다. 

2) 이 문제를 해결하기 위해, 따로 2차원 배열을 생성하여 *문자를 저장하는 방법과 바로 출력하는 방법이 존재한다고 생각했다.  나는 후자를 선택하여 문제를 풀었다.

3) 먼저 공백의 조건을 파악해보자. 3x3 사각형 일 때는 (1,1)이 공백이 되어야한다.  ( x % 3  == 1) && ( y % 3 == 1 ) 의 조건을 만족하는 것을 알 수 있고, 9x9의 x가 3일 때 까지도 위의 조건을 만족하지만, 가운데 큰 공백 조건을 만족하지 않는다.
가운데 큰 공백은 (3,3) (3,4) (3,5) (4,3) (4,4) (4,5) (5,3) (5,4) (5,5) 인데, N의 크기에 가운데 큰 공백의 크기가 달라지기 때문에 N을 이용해야한다. 따라서  ((x / n) % 3 == 1 && (y / n) % 3 == 1)을 이용해서 큰 공백의 조건을 만족할 수 있다. 

4) 내가 생각하기엔 재귀 문제는 말로 설명을 듣는 것 보단 코드를 보는게 이해가 빠르다고 생각하기에 코드를 보고 이해하는 것을 추천한다. 

#include <iostream>
using namespace std;
int n;

void solve(int n, int x, int y)
{
    if ((x / n) % 3 == 1 && (y / n) % 3 == 1)
        cout<<" ";
    else
    {
        if (n / 3 == 0)
            cout<<"*";
        else
            solve(n/3, x ,y);
    }
    return;
}
int main(void)
{
    cin>>n;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            solve(n,i,j);
        }
        cout<<"\n";
    }
}