백준 2448번: 별 찍기 - 11 (C++)

문제 링크는 다음과 같다.

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

2448번: 별 찍기 - 11

 

별 찍기 10번 문제와 굉장히 유사한 문제이다.

 

10번을 확실하게 이해했다면 11번은 무난하게 풀 수 있을 것이다.

 

n = 6인 경우는, n = 3인 경우의 삼각형 세 개가 반복되고,

 

n = 12인 경우는, n = 6인 경우의 삼각형 세개가 반복돼서 찍힌다. 

 

즉 n인 경우는 3개의 n-1인 경우로 이루어진다는 것을 알 수 있다.

 

따라서 알고리즘을 구현할 때도, 세 단계로 나눠서 재귀함수를 구현해주면 되겠다.

 

문제를 파악하면서 알 수 있듯이, base condition은 n = 3인 경우라는 것을 알 수 있다.

 

여러 가지 방법이 있겠지만, 생각의 편의성을 위해서 1 - indexed로 풀이를 진행했다.

 

최대 크기의 char 배열을 미리 잡아두었다.

 

base condition을 확인할 때 크기 정보를 사용하기 때문에(3인 경우 탈출) 크기를 인자로 갖고 있어야 한다.

 

또한 어느 좌표에 별을 찍을 것인지 확인이 필요하기 때문에 row와 col을 추가적으로 인자로 받는다.

 

그리고 공백인 부분에 대해서는 따로 신경을 쓰지 않고, 별을 모두 찍은 이후에 일괄적으로 공백에 대한 처리를 해주었다.

 

고등학교 수학에서 흔히 프렉탈이라고 불렀던 문제 유형과 생각의 흐름이 비슷한 것 같다는 느낌을 받았다.

 

#include<iostream>
using namespace std;
char arr[3073][6145];
void func(int n, int r, int c) {
	//base condition
	if (n == 3) {
		arr[r][c] = '*';
		arr[r + 1][c - 1] = '*';
		arr[r + 1][c + 1] = '*';
		for (int i = c-2; i <= c+2; i++)
			arr[r + 2][i] = '*';
		return;
	}
	
	func(n / 2, r, c);
	func(n / 2, r + n / 2, c - n / 2);
	func(n / 2, r + n / 2, c + n / 2);
	
}
int main(void) {
	
	int N;
	cin >> N;

	//1-indexed;

	func(N,1, N); //n, row, col
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 2 * N - 1; j++) {
			if (arr[i][j] != '*')
				arr[i][j] = ' ';
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 2 * N - 1; j++) {
			cout << arr[i][j];
		}
		cout << '\n';
	}
	return 0;

}