BOJ 2447 - 별 찍기 - 10

문제 링크

문제#

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력#

첫째 줄에 $N$이 주어진다. $N$은 3의 거듭제곱이다. 즉 어떤 정수 $k$에 대해 $N = 3^k$이며, 이때 $1 \le k < 8$이다.

출력#

첫째 줄부터 N번째 줄까지 별을 출력한다.

풀이#

전체 도형을 한 번에 그리는 것이 아니라, 더 작은 기본 패턴을 재귀적으로 배치한다고 생각하면 된다. 문제에서 요구하는 별 모양이 자기 유사 구조를 갖기 때문에 분할 정복이 자연스럽다.

코드에서는 현재 크기의 패턴을 여러 개의 하위 패턴으로 나누어 배치하고, 비워야 할 칸이나 채워야 할 칸만 규칙대로 처리한다. 가장 작은 기본 크기에서는 직접 별을 그리며 종료한다.

즉 출력량은 많지만 아이디어 자체는 재귀 패턴 생성이다.

코드#

#include <iostream>
using namespace std;
 
int n;
 
void printStar(int i, int j, int n) {
	
	if ((i / n) % 3 == 1 && (j / n) % 3 == 1)
		cout << " ";
 
	else {
		if (n < 3)
			cout << "*";
		else
			printStar(i, j, n / 3);
	}
 
}
 
void solve() {
	
	cin >> n;
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			printStar(i, j, n);
 
		cout << '\n';
	}
 
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	solve();
 
	return 0;
}

복잡도#

• 시간 복잡도: 출력해야 하는 $N \times N$ 문자를 채우므로 $O(N^2)$이다.
• 공간 복잡도: 그림 저장 배열을 사용하므로 $O(N^2)$이다.

마무리#

별 찍기 문제는 결국 패턴을 얼마나 잘 쪼개서 다시 놓느냐의 문제다. 기본 모양과 재귀 배치 규칙만 잡으면 큰 그림도 그대로 따라온다.