(c++)백준 2447번: 별 찍기 - 10

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

2447번: 별 찍기 - 10

[풀이]

분할 정복을 이용한 별 찍기 문제였다.

가장 작은 단위는 N이 3일 때

이고, 빈칸의 좌표는 (1,1)이다.

기본 단위가 여러개 붙어있으면

이와 같은 모양이고, 빈칸의 좌표는 (1,1), (1,4), (1,7), (1,10), (1,13), (1,16), (1,19), (1,22), (1,25)이다. 

즉, x%3=1이고, y%3=1인 좌표에서 빈칸이 나와야 한다.

 

N이 9인 경우를 보면

이런 형태이고, 가운데 빈칸의 좌표는 (3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)이다.

즉, (x / (9 / 3)) % 3 = 1이고, (y / ( 9 / 3 )) % 3 = 1인 좌표에서 가운데 빈칸이 나와야 한다. (=3*3형태가 한 번 나오고, 빈칸이 나오므로)

 

위와 같은 조건을 재귀적으로 반복하면 답이 나온다.

 

#include <iostream>
using namespace std;

//사이즈를 3으로 나눠가면서 검사
void printStar(int x, int y, int n) {
	//(현재 크기/3)*(현재 크기/3)패턴이 한 번 나온 후 공백
	if ((x / n) % 3 == 1 && (y / n) % 3 == 1) {
		cout << ' ';
	}
	//더 이상 3으로 나누어지지 않으면
	else if (n / 3 == 0)
		cout << '*';
	//더 작은 단위 검사
	else
		printStar(x, y, n / 3);
}

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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printStar(i, j, N);
		}
		cout << endl;
	}
	return 0;
}