2448번

2448번 - 별찍기 - 11

유사한 삼각형이 반복되고 있기 때문에, 분할정복 과 재귀를 이용해서 문제를 풀었다.

makeTri 에서는 이 삼각형까지 최소로 찾아내고,

makeSmallTri 에서는 이 삼각형을 그려내는 방식으로 문제를 풀었다.

분할을 두번 사용했는데... 사실 이렇게 까지 해서 푸는게 맞는 방식인지는 모르겠다. 내 판단대로 풀었다.

그런데 큰 삼각형 분할해서 재귀를 들어갈 때,  제일 작은 삼각형이랑 큰 삼각형이랑 재귀가 맞지 않다고 생각했다.( 합동이 아니다는 뜻)

왜냐하면 작은 삼각형은 맨 아랫줄은 꽉 차 있지만, 큰 삼각형은 한칸이 비어있기 때문에 재귀로 다시 더 들어갈 수 없다고 생각했다.

그래서 큰 삼각형까지 최대한 줄이고 (n ==6 이 될 때까지, n은 삼각형의 아랫변이 아닌 빗변의 길이) , 그 안에서 작은 삼각형을 찾도록 하였다.

배열을 이용하였고, 작은 삼각형은 dx, dy 배열을 이용해서 별을 표시하는 모든 칸을 표시하였다.

그리고 그러다보니 입력값으로 3이 들어왔을 때는 그냥 처리를 해줘야 했다. 예외로.

##다른 분들 코드도 한번 보고 이해하고 와야겠다.

<정답 코드>

#include<iostream>
 
using namespace std;
 
int N;
int dx[9] = { 0,1,1,1,2,2,2,2,2 };
int dy[9] = { 0,-1,0,1,-2,-1,0,1,2 };
bool map[6145][6145];
void makeSmallTri(int x, int y)
{
 
    for (int d = 0; d < 9; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        
        if (d != 2)
        {
            map[nx][ny] = true;
        }
    }
    return;
}
 
void makeTri(int x, int y, int n)
{
    if (n == 3)
    {
        makeSmallTri(x, y);
        return;
    }
    if (n == 6)
    {    
 
        makeSmallTri(x, y);
        makeSmallTri(x + 3, y - 3);
        makeSmallTri(x + 3, y + 3);
 
        return;
    }
 
    int nn = n / 2;
    makeTri(x, y, nn);
    makeTri(x + nn, y - nn, nn);
    makeTri(x + nn, y + nn, nn);
 
    return;
 
}
int main()
{
    cin >> N;
 
    makeTri(0, N - 1, N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 2 * N; j++)
        {
            if (map[i][j])
            {
                cout << "*";
            }
            else
            {
                cout << " ";
            }
        }
        cout << endl;
    }
 
    return 0;
}