BaekJoon(2447)::별찍기-10

문제

2447번: 별 찍기 - 10

문제파악

1. 재귀적인 패턴으로 별이 찍혀있음(N은 3의 거듭제곱)
2. 크기 3의 패턴은 가운데 공백이있음.
3. 해당 패턴이 재귀에 따라서 커지면서 반복됨.

문제의 기본이 되는 가장작은 사이즈는 우측그림에서 보다시피 초록색영역으로 출력이 된다. 

 

다만 재귀의 형태를 좀더 자세히 보고자 N=9로 확장해보면 파랑색영역으로 보이는것을 알 수 있고 그보다 크 27일때는 빨강의 영역이다.

 

그리고 별찍기의 특성상 별이 그려지면 탈출을 시켜주고 해당영역이 별이 찍히는지 여부가 판단이 안되면 재귀로 좀더 작은 형태에서 문제를 확인하면 됨을 알 수가 있다.

 

N의 사이즈가 커지면 i는 1, 4, 7, 9 등이 되며 i % 3==1 을 알 수 있다

그리고 j 또한 동일하게 j %3 == 1 으로 i % 3==1 &&  j %3 == 1 은 공백임을 알수가있다.

 

N이 커지면 중앙부의 사각 영역또한 늘어나는데 이것을 보면

N이 9일때는 (3,3) (3,4), (3,5), (4,3) (4,4), (4,5), (5,3) (5,4), (5,5) 가 가운데 영역이 된다. 이를 위 N이 3일때와 비교를 하면 (i / 3) % 3==1 &&  (j /3 ) %3 == 1 결국 이 또한 (i / N) % 3==1 &&  (j / N) %3 == 1 으로 확장해서 볼 수 있다.

 

해당 조건식을 재귀적으로 살펴보면 N으로 검사시 만족한다면 N/3으로 진행을 해도 같은 결과이기 때문에 빈칸으로 출력을 하면 되고 N/3==0인 경우는 더이상 공백이 아니기 때문에 별을 찍어주면 된다 그리고 나머지 모든 케이스에 대해서는 print_star(i, j, n/3)으로 전달하여 검사를 진행하면 되었다.

문제풀이

#include <iostream>
using namespace std;

void print_star(int i, int j, int n) {
    if ((i / n) % 3 == 1 && (j / n) % 3 == 1) {
        cout << ' ';
    }
    else if (n / 3 == 0) {
        cout << '*';
    }
    else {
        print_star(i, j, n / 3);
    }
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n;i++) {
        for (int j = 0; j < n; j++) {
            print_star(i, j, n);
        }
        cout << endl;
    }
}