[백준] 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=3k이며, 이때 1 ≤ k < 8이다.

출력

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

예제 입력 1

27

예제 출력 1

알고리즘 [ 접근방법 ]

결론부터 말하면 내힘으로는 못풀었다. 재귀함수를 어떻게 활용해야 할지 감은 잡았지만 디테일한 부분을 생각해내지 못했다.. 처음에는 이중 for문을 활용해 3x3형태의 별을 출력한 뒤 가운데 구멍을 뚫고 for문에서 재귀함수를 활용해보려고 했는데 가운데 구멍을 뚫는 부분에 어떤 코드가 들어가야 할지 감이 안잡혔다.

그래서 구글링을 통해 가장 쉽고 간결하게 짜인 코드를 찾아봤는데 솔직히 아직도 잘 이해가 안간다.. 학교에서 알고리즘을 배울 때도 재귀함수는 진짜 이해가 안갔는데 역시나 어렵다..

자료를 찾아보니 재귀 + 분할정복(Divide and Conquer) 문제라고 하는데 좀더 알고리즘 공부를 한뒤 다시 풀어봐야 할 것 같다.

출처 : https://cryptosalamander.tistory.com/38

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>


void star(int i, int j, int test) {

	if ((i / test) % 3 == 1 && (j / test) % 3 == 1) printf(" ");
	else {
		if (test / 3 == 0) printf("*");
		else star(i, j, test / 3);
	}
}



int main() {
	int num = 0;

	scanf("%d", &num);

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