[C++] 백준 2447번 별 찍기 - 10

별을 찍는 문제입니다.

3의 n제곱으로 입력을 받습니다.

3의 입력값은 다음 모양을 가집니다.

★	★	★
★		★
★	★	★

9의 입력값은 다음 모양을 가집니다.

★	★	★	★	★	★	★	★	★
★		★	★		★	★		★
★	★	★	★	★	★	★	★	★
★	★	★				★	★	★
★		★				★		★
★	★	★				★	★	★
★	★	★	★	★	★	★	★	★
★		★	★		★	★		★
★	★	★	★	★	★	★	★	★

여기서 알 수 있는점은

3은 가운데가 비어있고 나머지를 별로 채운 모양입니다.

9는 3*3모양씩 잘라서 생각했을때 가운데가 비어있고

     나머지는 3을 입력했을때의 모양으로 채워져있습니다.

27을 입력한다면 9*9의 모양으로 잘라서 보았을때 가운데가 비어있고 

       나머지는 9를 입력했을때의 모양으로 채워져 있을것입니다.

 

이 문제는 분할 정복 알고리즘으로 문제를 해결합니다.

 

n*n배열을 만들어주어서 그 배열에 공백으로 가득채웁니다.

3의 제곱값을 입력받고 그 값을 3으로 나누어서 1이 될때까지 나눕니다.

1이 될때까지 나누어진 값들은 배열에 *을 채워줍니다.

1이 되지 못하는 경우는 i와 j가 1일때인데 이는 현재 n*n배열에서 중앙을 의미합니다.

모든값들이 배열에 입력되었으면 출력해주면서 별 찍기를 완성합니다.

 

#include <iostream>
using namespace std;

char map[3000][3000];

void init() {
	for (int i = 0; i < 3000; ++i) {
		for (int j = 0; j < 3000; ++j) {
			map[i][j] = ' ';
		}
	}
}

void solve(int n, int x, int y) {
	if (n == 1) {
		map[x][y] = '*';
		return;
	}
	int div = n / 3;
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			if (i == 1 && j == 1) {
				continue;
			}
			solve(div, x + (div * i), y + (div * j));
		}
	}
	return;
}

int main(int argc, char *argv[])
{
	int n;
	cin >> n;

	init();
	solve(n, 0, 0);

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

	return 0;
}