[Divide and Conquer] 백준 2447번 “별 찍기 - 10” C++ 풀이

문제 링크

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

풀이

• N 은 반드시 3의 거듭제곱(3, 9, 27, ...)입니다.

• 따라서, 우선 작은 N 을 가지는 정사각형에 별을 찍어보며, 어떤 좌표값이 공백인지를 확인해, 공백인 좌표를 일반화 해야합니다.

  • N=3

    

    • 3x3 크기 기준, 중앙 공백 좌표
      • (1, 1)
        • i % 3 == 1 && j % 3 == 1

  • N=9

    

    • 9x9 크기 기준, 중앙 공백 좌표
      • (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)
        • (i / 3) % 3 == 1 && (j / 3) % 3 == 1
    • 3x3 크기 기준, 중앙 공백 좌표
      • (1, 1), (1, 4), (1, 7), (4, 1), (4, 4), (4, 7), (7, 1), (7, 4), (7, 7)
        • (i / 1) % 3 == 1 && (j / 1) % 3 == 1
    • 즉, 크기 N 의 정사각형 중앙 공백 좌표는 아래와 같이 일반화할 수 있습니다.
      • (i / (N/3)) % 3 == 1 && (j / (N/3)) % 3 == 1

• 따라서, 크기 N 의 정사각형으로부터의 공백 좌표 탐색은, 큰 크기의 정사각형부터 작은 크기의 정사각형 순으로 탐색됩니다.

  1. i,j 좌표가 크기 N 의 정사각형 기준으로 중앙 공백 좌표인지 확인
  2. 아니라면, 정사각형의 크기를 N/3 으로 줄인 뒤, N/3 정사각형 기준으로 중앙 공백 좌표인지 확인
  3. 1~2 과정을 반복하며 i, j 가 중앙 공백 좌표인 경우에는 공백을 출력
     • N 의 크기가 1 이 된 경우에는, 더 이상 탐색할 수 있는 공백이 없으므로 * 출력

코드

#include <iostream>

using namespace std;

// 좌표에 대한 공백 여부 탐색
void check_blank(int i, int j, int n){

    // 현재 탐색하고 있는 N X N 정사각형의 크기가 1 이라면, 
    // 더 이상 탐색할 수 있는 공백이 없으므로 * 출력
    if (n == 1){
        cout << "*";
    }
    // 현재 탐색하고 있는 N X N 정사각형의 크기가 3 이상이고,
    // i,j 좌표가 해당 정사각형의 중간에 위치하고 있다면, 공백 출력
    else if ((i / (n/3)) % 3 == 1 && (j / (n/3)) % 3 == 1){
        cout << " ";
    }
    // 현재 탐색하고 있는 N X N 정사각형의 크기가 3 이상이고, 위 과정에서 공백을 찾지 못했다면
    // 탐색하고자하는 정사각형의 크기를 N/3 으로 줄인 뒤, 해당 정사각형 기준으로 중간에 위치한 공백인지 재탐색
    else{
        check_blank(i, j, n/3);
    }
}

int main(){
    // 정사각형 크기 입력
    int n;
    cin >> n;

    // 정사각형이므로 이중 포문 탐색
    for (int i=0; i<n; ++i){
        for (int j=0; j<n; ++j){
            check_blank(i, j, n);
        }
        cout << endl;
    }

    return 0;

}

참고

• https://codesyun.tistory.com/75