[백준 / BOJ] - 2447번 별 찍기 -10 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [2447] 

https://www.acmicpc.net/problem/2447

문제

 

 

위 그림과 같은 규칙성을 가지는 프렉탈 도형에서, 3의 제곱수인 임의의 값 N을 입력받았을 때, 

N*N의 그림을 재귀적으로 출력하는 문제이다.

 

풀이

 

프렉탈 도형 문제는 일반적으로 분할정복 방법을 사용할 수 있다.

 

N = 3일 경우,

 

 

위와 같은 형태가 기본 단위가 된다. 이 때 항상 가운데가 비어 있게 되는데 비어 있는 부분의 좌표는 (1, 1)로 표현될 수 있으며 

 

 

위와 같은 형태에서 비어있는 좌표는 (1,1) , (1,4) , (1,7) , (1,10) , ... , (1, 25)이다.

따라서 가장 기본적인 단위에서의 규칙을 만족시키기 위한 조건은

i%3 == 1 && j%3 == 1 이다.

 

N = 9 일 경우,

 

 

위와 같은 모양을 가지게 되는데, 이 때 중요하게 봐야 할 것은 N = 3일때의 기본단위의 모양이 크기만 커졌지, 결국 가운데가 비어있다는 같은 규칙을 띈다는 것이다. 

 

이 때 비어있는 가운데 좌표는, (3,3) (3,4) (3,5) (4,3) (4,4) (4,5) (5,3) (5,4) (5,5) 이다.

이를 수식으로 표현하면, 3x3의 기본단위 모형이 한개 나온 후, 비어있다는 표현이므로

 

(i / 3) % 3 == 1 && (j / 3 ) % 3 == 1의 조건을 만족시키면 된다.

 

이러한 재귀적 반복을 코드로 구현하면 풀 수 있는 문제이다.

 

 

 

 

코드

 

#include <iostream>
using namespace std;
void star(int i, int j, int num)
{
    if((i / num)%3 == 1 && (j / num)%3 == 1) {
        cout << ' ';
    }
    else
    {
        if(num / 3 == 0)
            cout <<'*';
        else
            star(i,j,num/3);
    }
}
int main() {
    int num;
    cin >> num;
    for(int i = 0; i < num; i++)
    {
        for(int j = 0; j < num; j++)
            star(i,j,num);
        cout << '\n';
    }
}

 

평가

 

비록 문제 자체의 난이도는 높지 않지만,

그래도 별 찍기 문제 중에서는 난이도 최상이라고 볼 수 있는 분할 정복 기반의 별찍기이다.

재귀적 반복 규칙을 찾는 것이 까다로울 수 있지만, 규칙만 찾아내면 쉽게 풀 수 있는 문제이다.

핵심은 입력받은 사이즈를 3으로 나눠가면서 점점 작은 단위로 검사하는 과정이다.