BOJ 2447 별 찍기 - 10 C++

문제

N의 범위를 보니 배열에 저장하는 것은 좋지 않아 보인다.

 

접근 방법

🌟 index를 가지고 규칙을 찾는다.

🌟 재귀를 이용한 분할 정복의 냄새가 난다.

 

1️⃣ N == 3

	0	1	2
0	*	*	*
1	*		*
2	*	*	*

 

정사각형의 가운데인 (1,1)이 비었다.

 

2️⃣ N == 9

	0	1	2	3	4	5	6	7	8
0	*	*	*	*	*	*	*	*	*
1	*		*	*		*	*		*
2	*	*	*	*	*	*	*	*	*
3	*	*	*				*	*	*
4	*		*				*		*
5	*	*	*				*	*	*
6	*	*	*	*	*	*	*	*	*
7	*		*	*		*	*		*
8	*	*	*	*	*	*	*	*	*

 

여기서 구멍난 부분들은 둘로 구분할 수 있다.

#1. (1,1), (1,4), (1,7), (4,1), (4,7), (7,1), (7,4), (7,7)

#2. (3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)

첫 번째 그룹은 3 사이즈의 정사각형의 가운데가 뚫린 것이고, 

두 번째 그룹은 9 사이즈의 정사각형의 가운데가 뚫린 것이다.

 

가장 큰 사이즈의 정사각형의 가운데에 속하는지 확인한 후, 맞다면 공백을 출력하면 되고, 

아니라면 계속해서 더 작은 사이즈의 가운데에 속하는지 확인하면 된다.

---

#1. (1,1), (1,4), (1,7), (4,1), (4,7), (7,1), (7,4), (7,7)

#2. (3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)

 

 

N이 9일 때 #2을 걸러내야 한다.

x좌표, y좌표 모두 3, 4, 또는 5이다.

3으로 나눈 값이 1이라는 공통점이 있다.

 

하지만 만약 N이 27이라면 N = 9로 인해 생긴 구멍은 8개로 늘어나기 때문에, 단순히 나눈 값이 1이라고 해선 안 된다.

(12,3), (12,4), ..., (21, 3), (21,4), ..., (23,23)와 같은 좌표도 커버해야 한다.

이때 x좌표, y좌표의 도메인은 {3,4,5,12,13,14,21,22,23}이 된다.

3으로 나눈 값의 3에 대한 나머지가 1이라는 공통점이 있다.

 

 

N이 3일 때 #1를 걸러내야 한다.

x좌표, y좌표 모두 1, 4, 또는 7이다.

3에 대한 나머지가 1이라는 공통점이 있다고도 할 수 있지만, 표현을 바꿀 수 있다.

1으로 나눈 값의 3에 대한 나머지가 1이라는 공통점이 있다.

참고로 이때 (4,4) 좌표에 대해서는 걱정할 필요가 없다. 어차피 그 이전에(N = 9 에서) 처리가 될 것이니까.

 

소스 코드

#include <iostream>
using namespace std;

void print_star(int n, int x, int y) 
{
    if (n == 1)
        cout << '*';
    else if((x*3/n) % 3 == 1 && (y*3/n) % 3 == 1)
        cout << ' ';
    else
        print_star(n/3, x, y);
    return;
}

int main()
{
    int N; cin >> N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++)
            print_star(N, i, j);
        cout << '\n';
    }
    return 0;
}