[BOJ/C++] 2447 - 별 찍기 10

문제

BOJ 2447 - 별 찍기 10

// 입력
27

// 출력
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

코드

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<char>> stars;

void middle_blank(int x, int y, int length) {
	if (length == 1)
		return;

	length /= 3;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
        	// 중간 사각형만 공백 처리 
			if (i == 1 && j == 1) {
				for (int a = length; a < 2 * length; a++) {
					for (int b = length; b < 2 * length; b++) {
						stars[x + a][y + b] = ' ';
					}
				}
			}
			else {
				middle_blank(x + i * length, y + j * length, length);
			}
		}
	}
}

int main() {
	cin >> n;

	stars.resize(n, vector<char>(n, '*'));

	middle_blank(0, 0, n);

	for (int i = 0;i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << stars[i][j];
		}
		cout << endl;
	}

	return 0;
}

• 시간 복잡도: $O(N^2)$
• 분할 정복
• 정사각형을 9등분 (divide)하여 중간의 정사각형을 공백처리한다.