[백준 BOJ] 2448. 별 찍기 - 11

난이도

Gold IV

문제 풀이

예제 데이터를 보고 규칙을 추론해서 별을 찍는 문제이다. N = 24 일때의 데이터만 주어지는데 큰 블록으로 보면 3개의 삼각형이 하나의 큰 삼각형을 이루는 것을 쉽게 알 수 있다. 그리고 작은 삼각형 내부에도 또 다른 3개의 삼각형으로 그 삼각형을 이루고 있는걸 보면 재귀적인 구조로 이루어진다는 사실 또한 쉽게 캐치할 수 있다. 구조가 재귀적이니 풀이도 재귀함수를 사용하는 편이 편할 것이다. 먼저, 재귀함수를 만들기 전에 어떻게 그려야 할 지 생각을 해보도록 하자.

가장 작은 삼각형은 N = 3일때이다. 예제 데이터에서 잘 보면

  *                        
 * *                       
*****

이렇게 생긴 삼각형이 N = 3일때라는 것을 쉽게 파악 할 수 있을 것이다. 그렇기에, 재귀를 종료 시키는 N = 3이 되는 시점에는 저 삼각형을 넣어주고 함수를 종료시키면 된다. 그럼, 나머지는 어떻게 해야할까..? 잠시 그림을 보고 생각을 해보자.

가장 위에 있는 삼각형의 윗쪽 꼭지점 좌표를 \(\scriptsize (x, y)\)라고 해보자. 그럼, 좌측 아래 삼각형의 윗꼭지점 좌표는 \(\scriptsize (x - \frac {N} {2} , y + \frac {N} {2})\)이 된다. 우측 아래 삼각형 윗꼭지점 좌표는 \(\scriptsize (x + \frac {N} {2} , y + \frac {N} {2})\) 이렇게 된다. 즉, 어떤 삼각형이 주어지면 저렇게 좌표로 삼각형을 찢으면서 그려줄 수 있다. 삼각형을 그리는 함수를 \(\scriptsize f(N, x, y)\)라고 해보자. N은 삼각형의 크기이고 x, y는 각각 좌표이다. \(\scriptsize f(N, x, y)\)을 \(\scriptsize (x, y)\)에서 부터 시작하는 N 크기의 삼각형이라고 하면, 다음과 같은 점화식으로 표현 할 수 있다.

\[\scriptsize f(N, x, y) = f(N / 2, x, y) + f(N / 2, x - N / 2, y + N / 2) + f(N / 2, x + N / 2, y + N / 2), (N \neq 3)\]

\(\scriptsize f(N, x, y) =\) 가장 작은 삼각형, \(\scriptsize (N = 3)\)

이렇게 점화식을 찾아내었으니, 이를 재귀함수로 작성해보자. 다음과 같이 짤 수 있겠다.

vector<vector<char>> baseTriangle =
{
    {' ', ' ', '*', ' ', ' '},
    {' ', '*', ' ', '*', ' '},
    {'*', '*', '*', '*', '*'} 
};

void solve(int N, int x, int y, vector<vector<char>>& map) {
    if(N == 3) {
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 5; ++j) {
                map[y + i][x - 2 + j] = baseTriangle[i][j];
            }
        }
        return;
    }

    solve(N / 2, x, y, map);
    solve(N / 2, x - N / 2, y + N / 2, map);
    solve(N / 2, x + N / 2, y + N / 2, map); 
}

먼저 N = 3일때의 삼각형을 미리 저장해두고, N = 3일때 해당 좌표에 그 문자들을 모두 대입하는 방식으로 짰다. N != 3일때는 위에서 찾아낸 점화식을 수행하도록 짠 것이다.

처음 함수를 호출 할때는 solve(N, N - 1, 0, map) 으로 호출하면 된다. (N - 1, 0)이 처음 시작 좌표이기 때문이다. 대체로 이런류의 문제는 점화식을 찾아내면 빨리 풀리는 듯 하다.

코드 전문

2448 // 별 찍기 - 11