Baekjoon[C언어] - 2447번 별찍기 - 10

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

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은 모두 3의 제곱수로 주어질 것이며, 

문제는 재귀적인 패턴을 도출해내는 문제이므로, 분할정복 방법을 사용하여 풀어낼 것이다.

 

크기 3의 패턴은 언제나 가운데에 공백이 있으며, (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이므로,

***
* *
***

위와 같은 형태가 반복되며, 

*********
* ** ** *
*********
***   ***
* *   * *
***   ***
*********
* ** ** *
*********

N이 9일 경우 중앙에 더 큰 공백이 생기며 위와 같이 그려진다.

 

공백이 나오는 부분의 좌표를 (1, 1)이라고 하면, N이 9인 경우엔

(4, 1), (7, 1) 등의 좌표 또한 공백이 된다.

( 3 X 3 )의 기본형이 반복되는 것.

 

이 좌표들이 공통점을 계산해보면,

(x, y)라고 가정했을 때,

x % 3 == 1 && y % 3 ==1

가 성립하는 경우에 공백이라고 할 수 있다.

 

여기서, 하나 더 생각해주어야 할 것은 위처럼 공백이 계속해서 기본형의 공백만 반복되는 것이 아닌

위에 표시된 구간 또한 공백이다.

(3,3) (3,4) (3,5) (4,3) (4,4) (4,5) (5,3) (5,4) (5,5)의 좌표들로 이루어진 공백인데,

N / 3 ≤ x or y < 2N / 3

의 규칙을 찾을 수 있다.

 

살짝 정리해보면,

(x or y) / N = 1

일 때 공백이라는 것을 유도해낼 수 있다.

 

지금까지 얻은 규칙을 바탕으로 조건문을 작성해보면,

(row / N) % 3 == 1 && (col / N) % 3 == 1

위와 같이 작성할 수 있겠다.

void starboxMaker(int row, int col, int N) {
	if ((row / N) % 3 == 1 && (col / N) % 3 == 1) {
		printf(" ");
	}
	else {
		if (N / 3 == 0) {
			printf("*");
		}
		else {
			starboxMaker(row, col, N / 3);
		}
	}
}

해당 조건이 성립할 때만 공백을 출력하고,

N이 3보다 작은지 확인하고 그렇다면 *을 출력하고 아니라면

N을 3으로 나눠서 다시 함수를 호출해준다.

#include <stdio.h>

// 2447 별 찍기

void starboxMaker(int row, int col, int N);

int main() {
	int N;
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			starboxMaker(i, j, N);
		}
		printf("\n");
	}

	return 0;
}

void starboxMaker(int row, int col, int N) {
	if ((row / N) % 3 == 1 && (col / N) % 3 == 1) {
		printf(" ");
	}
	else {
		if (N / 3 == 0) {
			printf("*");
		}
		else {
			starboxMaker(row, col, N / 3);
		}
	}
}

성공!