뚝딱뚝딱

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

💡 별 찍기 -10

✅ 문제 풀이

• 프렉탈 도형 문제
• 재귀함수를 사용한 분할과 정복으로 해결할 수 있다
• 도형의 패턴을 분석해보자.

위는 N=3일때의 도형의 출력 형태이다. 좌표로 따졌을 때 (1,1)만 비어있음을 알 수 있다.

위는 N=9일때의 도형의 출력 형태이다. 좌표로 따졌을 때 (1,1),(1,4),(1,7),(3,3),(3,4),(3,5),(4,1),(4,3),(4,4),(4,5),(4,7),(5,3),(5,4),(5,5),(7,1),(7,4),(7,7)이 비어있음을 알 수 있다.

좌표를 보니,  (i/3)%3==1 과 (j/3)%3==1을 만족하는 경우에 비어있음을 확인할 수 있다.

또한 3*3 개별 도형들의 빈 자리는 (i/1)%3==1 과 (j/1)%3==1을 만족하는 경우에 비어있음을 확인할 수 있다.

따라서 중간에 나누어 지는 값은 3*3 도형이 한 변에 만들어지는 개수로 생각할 수 있고, 이는 n을 3으로 나누어가며 위의 공식에 만족할 경우 " "를, 그렇지 않으면 *을 출력하도록 하면 된다.

즉, *이 출력되는 경우는 위의 공식을 만족하지 않는 위치일 경우, 별을 하나 출력한다고 생각하면 되고, 그때마다 3*3 하나를 기준으로 하므로 num은 1이 될 것이다.

✏ 코드 전문

#include<iostream>

using namespace std;

void star(int i, int j, int num) {
	if ((i / num) % 3 == 1 && (j / num) % 3 == 1) {
		cout << " ";
	}
	else {
		if (num / 3 == 0) {
			cout << "*";
		}
		else {
			star(i, j, num / 3);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			star(i, j, n);
		}
		cout << "\n";
	}

	return 0;
}