[백준 / BOJ] 2447번: 별 찍기

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

2447번: 별 찍기 - 10

 

 

---

코드

---

#include <iostream>
using namespace std;
void star(int i, int j, int n)
{
	//n이 1이라면 * 출력 후 리턴
	if (n == 1) {
		cout << '*';
		return;
	}
	//n 크기의 사각형에 대하여 가운데 공백구역에 있는지 조사
	if ((i / (n / 3)) % 3 == 1 && (j / (n / 3)) % 3 == 1) {
		cout << ' ';
	}
	//아니라면 n/3 크기의 사각형에 대한 공백 영역에 속하는지 검사하기 위해 재귀
	else star(i, j, n / 3);
	
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			star(i, j, n);
		}
		cout << '\n';
	}
}

 

 

---

 

 

기본적으로, 3의 거듭제곱 수인 n에 대해, for문을 돌며 모든 좌표에 해당하는 star 함수를 호출했다.

n*n 크기의 정사각형 좌표에 대해, 다음의 세가지 경우로 나누어 생각하였다.

1. n 크기의 정사각형에 대해, 가장 큰 공백영역에 속하는 좌표는 공백문자를 출력한다(출력 후 리턴).
2. n 크기의 정사각형에 대해, 가장 큰 공백영역에 속하지 않는 좌표라면, n/3 크기의 정사각형에 대한 가장 큰 공백영역에 속하는지 검사하기 위해 star(i, j, n/3) 함수를 호출한다.
3. n이 1일 때까지 호출된다면, 공백영역에 해당하는 좌표가 아니므로 * 을 출력한 후 리턴한다. 

여기서, 가장 큰 공백영역은 n=27일 때 9*9의 영역, n=9일 때 3*3의 영역을 나타낸다.

 

공백영역에 있는 좌표를 찾기 위한 수식을 표현하는데에 시간을 가장 많이 썼는데, 깔끔한 수식이 아닌것 같다..

아무튼 이 문제를 통해 분할정복 문제를 어떻게 해결하는지 감을 잡을 수 있었다.

 

검색했을 때 대표적으로 나오는 코드들이 훨씬 깔끔하니까 다시 복습할 때 참고하기!