[알고리즘] 백준 2447번 "별 찍기 - 10" - Don 임베디드

문제요약:

 

재귀함수를 이용하여 특정 규칙의 별을 찍어보자.

N이 3의 거듭제곱(3, 9, 27, 81, ...)이라고 할 때,

크기 N의 패턴은 길이 N짜리 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고,

가운데를 제외한 모든 칸에 별이 하나씩 있는 길이 N짜리 정사각형이다.

 

 

제약:

 

시간 제한 1초, 메모리 제한 256MB

N은 3의 거듭제곱이다. (N = 3^k)

이 때, 1 <= k < 8 이다.

 

 

예제 1 입력.	예제 1 출력.
3	*** * * ***
예제 2 입력.	예제 2 출력.
9	********* * ** ** * ********* ***   *** * *   * * ***   *** ********* * ** ** * *********

 

 

정답코드:

 

#include <iostream>
#define MAX_LENGTH      (6561)
 
using namespace std;
 
// "*"을 출력할 지 여부를 저장할 boolean array 생성.
bool aabStars[MAX_LENGTH + 1][MAX_LENGTH + 1] = { false, };
 
void checkStars(int X, int Y, int N)        // 위치, 네모의 크기를 받는 재귀함수.
{
    if (N == 1)
    {
        // N의 크기가 1이면, "*"을 출력하겠다는 표시를 하고 넘어감.
        aabStars[X][Y] = true;
        return;
    }
    else if (N <= MAX_LENGTH)
    {
        // N의 크기가 1이 아닌 경우, 루프를 돌면서 출력.
        //  - 규칙 1. N의 크기가 몇이든, 3x3 번 재귀함수를 호출한다.
        //  - 규칙 2. 3x3번 호출 중 중간은 재귀함수를 호출하지 않는다.
 
        for (int i = X; i < (X + N); i += (N / 3))
        {
            for (int j = Y; j < (Y + N); j += (N / 3))
            {
                if ((i == (X + (N / 3))) && (j == (Y + (N / 3))))
                { 
                    // 중앙부에 대해서는 출력하지 않음.
                    continue; 
                }
                else
                {
                    // 이외는 재귀함수 호출.
                    checkStars(i, j, N / 3);
                }
            }
        }
    }
    else
    {
        return;
    }
}
 
int main()
{
    int N;
    cin >> N;
 
    // 재귀함수를 호출하여 "*"을 출력할 대상을 체크.
    checkStars(0, 0, N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            // "*" 표시를 해야한다고 표시되어 있는 경우, 출력.
            if (aabStars[i][j] == true)
            {
                cout << '*';
            }
            else
            {
                cout << ' ';
            }
        }
        // 한 행이 끝나면 개행 출력.
        cout << '\n';
    }
}

 

원본 링크: https://www.acmicpc.net/problem/2447