분할 정복을 활용한 별 찍기 문제이다. 빈 칸이 나오는 경우의 패턴을 확인해보면 쉽게 문제를 풀 수 있다. 이번 문제 같은 경우는 정사각형의 중간 부분에 빈 칸이 찍히게 된다. n에 따른 빈칸 위치를 살펴보면 다음과 같다.
n | 빈 칸 |
---|---|
3 | (1,1) |
9 | (3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5) |
이를 통해 i/(n/3)%3==1 && j/(n/3)%3==1
과 같은 패턴을 확인할 수 있다. 이를 재귀로 구현해주면 끝이다.
#include <iostream>
using namespace std;
int N;
void star(int i, int j, int n) {
if (n == 1) {
cout << "*";
}
else if (i / (n / 3) % 3 == 1 && j / (n / 3) % 3 == 1) {
cout << " ";
}
else {
star(i, j, n / 3);
}
}
void solution() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
star(i, j, N);
}
cout << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
solution();
return 0;
}