2448번 별찍기-11 / C++

2448번: 별찍기-11 -> https://www.acmicpc.net/problem/2448

규칙 찾기 + 재귀함수 사용하기의 문제이다.

규칙은

3일때(k=1일때) 삼각형 하나

6일때(k=2일때) 앞의 3개로 구성된 큰삼각형 하나 ...

이런식으로 아래사진처럼 앞의 삼각형 3개로 이루어진 큰삼각형으로 변한다.

즉 가장 큰 삼각형에서 3개의 시작포인트에서 재귀를 해주면된다.

마지막으로 n=3(k=1)이되었을때는 작은 삼각형을 출력해주면된다. 

가장작은 삼각형은 삼각형 모양을 만들기위해 만든것같은데 보다시피 규칙을 적용할수가 없다.

이 알고리즘은 https://www.youtube.com/watch?v=WjmEVp-Lgns&t=720s 여기서 참고하였다.

처음에는 위의 삼각형을 찍고 아래줄에 똑같은 삼각형 2개를찍고 

위의 삼각형을 삼각형너비의 반만큼 밀어주는식으로 반복하려했으나 내실력으로 구현하기가 꽤나 어렵더라.

그래서 앞의 방식처럼 밀어주지않고 첫좌표를 찾아 거기서부터 반복하는 구성으로 만들기로 했다.

void star(int n, int x, int y)
{
    if (n == 3)                                    // n이 3이면 별찍기
    {
        t[y][x] = '*';
        
        t[y + 1][x - 1] = '*';
        t[y + 1][x + 1] = '*';
 
        t[y + 2][x - 2] = '*';
        t[y + 2][x - 1] = '*';
        t[y + 2][x] = '*';
        t[y + 2][x + 1] = '*';
        t[y + 2][x + 2] = '*';
    }
    else                                        // n이 3이 아니면 재귀함수
    {
        star(n / 2, x, y);
        star(n / 2, x-n/2, y+n/2);
        star(n / 2, x-n/2+n, y+n/2);
    }
}

우선은 별을 찍는 함수를 위와 같이 만들었다.

함수에 인자값을 3개를 받아 n은 그대로 N값, x와 y로는 시작지점의 꼭대기. 즉 첫번째 삼각형의 시작점을 주었다.

그리고 삼각형들을 보다보면 위와 같은 규칙을 찾을수 있다.

삼각형 3개의 시작점의 위치는 (x,y) (x-n/2, y+n/2) (x-n/2+n, y+n/2)가 되는것을 알수있다. 

즉 n=12라면 x=12, y=1이 된다.

char t[3072][6144];            // 세로 n, 가로 2n-1
 
main()
{
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)                    // 우선 공백으로 초기화
    {
        for (int j = 0; j < 2*n-1; j++)
        {
                t[i][j] = ' ';
        }
    }
 
    star(n, n-1, 0);                            // n값, x좌표, y좌표
 
    for (int i = 0; i < n; i++)                    // 출력
    {
        for (int j = 0; j < 2 * n -1; j++)
        {
            cout << t[i][j];
        }
        cout << "\n";
    }
}

k의 최대값은 10이므로 N의 최대값은 3072. 즉 세로 3072, 가로 6143이 최대크기가 된다

최대크기에 맞게 배열을 선언해준 후

값을 입력받고 값에 해당하는 범위만큼의 배열을 공백으로 초기화.

함수를 불러와 해당위치에는 별을 찍어줬다. (그부분만 공백값에서 덮어씌워짐)

(x, y에 n-1, 0을 준 이유는 배열은 0부터 시작이기때문에 1칸씩 당겨준 것)

그리고 다시 그만큼 출력하면 원하는 모양이 출력되게 된다.