[백준 2448] 별 찍기-11

문제 : 별찍기-11

문제 유형 : 분할 정복, 구현

별 찍는 규칙을 잘 찾아 별을 찍으면 되는 말로는 간단한 문제이다. 구현은 매우 간단하지만 삼각형의 규칙을 찾는게 어려웠다.

일단 예제 있는 걸로 규칙을 파악해보자. n이 24일때 별의 모양은 아래와 같다.

문제를 잘 읽어보니 n은 항상  (k는 10이하의 음이 아닌 정수) 인 수가 들어온다는 조건이 있다. 이를 보고 삼각형의 높이(세로)의 길이와 밑변(가로)의 길이를 세보았다. 

그랬더니 세로은 24즉 이고 가로은 (k=3)이라는 것을 알게 되었다. (여기서 가로에 별 5개와 띄어쓰기를 하나로 묶은 것이다.)

이제 가로를 4등분 하고 세로를 2등분 해보자.

여기서 n=24일때와 닮은 프렉탈 모양 3개가 보일 것이다. 이를 박스로 구분해보자.

맨 위에 있는 빨간색 사각형 안에 있는 삼각형으로 또 나눠보면 아래와 같다.

이러한 반복을 상자 안에 삼각형 모양이 하나만 있을때까지 나누면 아래와 같다.

이 정도면 규칙이 보일것이다. 크기가 어떤거든 나누는 기준은 아래와 같이 된다. 세로의 길이는 가장 작은 삼각형의 개수로 판단한 것이다.

이를 좌표를 통해 일반식을 구해보면 아래와 같이 된다. 

(오타 수정: (y + 2^(k-1), x)와 ( y + 2^(k-1), x+3*2^k)의 y좌표가 y + 2^(k-1)이 아닌 y + 3*2^(k-1)입니다.)

현재 삼각형을 사각형안에 넣었을때 맨 왼쪽 위를 (y, x)라 했을 때 그 다음 삼각형의 좌표들이다.

설명을 그림 위주로 아주 간단히 했지만 이해했을꺼라 생각한다.

이제는 분할정복을 하기 위해 간단히 식을 쓰고 소스코드를 작성해보자.

간단히 식을 세워보면 아래와 같다.

여기서 입력은 항상 인 수만 들어온다. 위 식에서 로 치환해보면 아래와 같이 단순한 식으로 바꿀 수 있다.

또는 아래와 같은 식으로 만들 수도 있다. (물론 위 식에서 분수로 표현 되어있는 것을 간단하게 바꾼 것이다.

이 함수를 가지고 소스코드를 짜보자.

#include<cstdio>
 
char DB[][6]=
{ "  *  ",
  " * * ",
  "*****" };
char MAP[3500][6500];
 
void solve(int n, int y, int x)
{
    if (n == 1)
    {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 5; j++)
                MAP[y + i][x + j] = DB[i][j];
        return;
    }
    solve(n / 2, y, x + 3 * n / 2);
    solve(n / 2, y + 3 * n / 2, x);
    solve(n / 2, y + 3 * n / 2, x + 3 * n);
}
 
int main()
{
    int n;
    scanf("%d", &n);
    solve(n / 3, 0, 0);
    for(int i=0;i<n;i++,puts(""))
        for(int j=0;j<2*n-1;j++)
            printf("%c", MAP[i][j] == '*' ? '*' : ' ');
    return 0;
}

이 문제를 꼭 재귀로 짜야할까? 그건 정해진것이 없다. 자신이 바로 생각나는걸로 짜면 되긴한다. 

이 재귀함수를 이용한 방식이 설명이 잘 되지 않는다면, chogahui05님의 블로그에서 반복문와 memset, memcpy를 이용한 풀이 방법도 있으니 한번 참고해보면 좋을꺼 같다.