백준 2447번: 별 찍기 - 10 (C++)

문제 링크이다.

 

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

2447번: 별 찍기 - 10

 

현재까지의 별 찍기 시리즈 중에서 가장 쓸만한 문제라고 생각한다. 10번까지 문제들 중에서 말이다.

 

n = 3일 때, n = 9일 때... 이렇게 차례로 생각해보자.

 

n = 3일 때, 9개의 칸중에서 가운데의 한 칸을 제외하고 나머지의 칸들에 별이 찍히게 된다.

 

즉 가운데가 빈다는 뜻이다.

 

n = 9인 경우와, 예시로 보여준 n = 27인 경우에도, 가운데가 크게 비어있는 것을 알 수 있다.

 

일단 이러한 패턴이 반복된다는 것을 알 수 있다.

 

그리고, n = 9인 상황을 그려내기 위해서는 n = 3인 상황을 9번(공백이 찍히는 것도 포함) 수행한다는 것을 알 수 있다.

 

즉 재귀를 활용해야겠다는 촉을 잡을 수 있다.

 

이전에 보았던 Z라는 재귀를 활용한 문제와 유사한 패턴이다.

 

때문에 유사한 방식을 사용해서 풀이를 진행했다.

 

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

char arr[2188][2188] = { ' ', };

void func(int len, int row, int col) {
	if (len == 3) {
		int cur = 0;
		for (int i = row; i < row + len; i++) {
			for (int j = col; j < col + len; j++) {
				if (cur == 4) {
					cur++;
					continue;
				}
				arr[i][j] = '*';
				cur++;
			}
		}
		return;
	}
	func(len / 3, row, col);
	func(len / 3, row, col + len / 3);
	func(len / 3, row, col + len / 3 * 2);
	func(len / 3, row + len / 3, col);
	//func(len / 3, row + len / 3, col + len / 3, ' ');
	func(len / 3, row + len / 3, col + len / 3 * 2);
	func(len / 3, row + len / 3 * 2, col);
	func(len / 3, row + len / 3 * 2, col + len / 3);
	func(len / 3, row + len / 3 * 2, col + len / 3 * 2);

}
int main(void) {
	
	//cout << pow(3, 7);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	func(n, 0, 0);
	
	//별이 아닌 부분 공백으로 채워줘야한다.
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] != '*')
				arr[i][j] = ' ';
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << arr[i][j];
		}
		cout << '\n';
	}
	return 0;
}

 

입력값의 범위에 맞게 최대 배열의 크기를 잡기 위해서 먼저 3의 7승의 값을 확인했었다.

 

재귀를 하면서 변하는 값들인 n과, row, col을 인자로 넘겨주었다. 

 

n = 3일 때를 base condition으로 두었다. 5번째 별이 찍힐 차례일 때 별을 찍지 않고 넘어가도록 처리를 해주었다.

 

앞서 언급했듯이, 재귀의 큰 흐름은 총 9단계에 거쳐서 진행된다. 그중 5번째에서 아무것도 찍지 않으면 된다.

 

아무것도 찍지 않았을 때 WA를 받아서, 혹시나 하는 마음으로 별이 아닌 곳에 공백을 찍어주는 작업을 했더니 정답처리를 받았다.