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

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

2448번: 별 찍기 - 11

[풀이]

분할 정복을 사용하여 풀어야 한다.

배열 star[N][2 * N - 1] 별을 저장한 다음 재귀함수에서 벗어나면 출력하는 방식으로 했다. 

아래와 같이 N이 가장 작은 수인 3일 때의 형태가 기본단위가 된다.

즉, N이 3이 될때까지 재귀를 돌리고, N이 3이 되면 기본단위를 그려주면 된다.

위 형태를 보면 제일 위의 꼭지점 좌표가 (x,y)라고 할 때(x=0, y=N-1),

각 기본단위의 꼭지점의 위치가 (x,y), (x + N/2, y - N/2), (x + N/2, y + N/2)인 걸 알 수 있다.

즉, N이 3이 아니면 위 3 꼭지점 좌표와 N/2를 인수로 하여 재귀를 하면 된다.

 

#include <iostream>
#include <cstring>//memset
using namespace std;

char star[3072][6144];//세로 N, 가로 2N-1

void printStar(int x, int y, int n) {
	//기본 별찍기
	if (n == 3) {
		star[x][y] = '*';
		star[x + 1][y - 1] = '*';
		star[x + 2][y - 2] = '*';
		star[x + 2][y - 1] = '*';
		star[x + 2][y] = '*';
		star[x + 2][y + 1] = '*';
		star[x + 2][y + 2] = '*';
		star[x + 1][y + 1] = '*';
	}
	else {
		printStar(x, y, n / 2);
		printStar(x + n / 2, y - n / 2, n / 2);
		printStar(x + n / 2, y + n / 2, n / 2);
	}
}

int main() {
	int N;
	cin >> N;
	//공백으로 초기화
	memset(star, ' ', sizeof(star));

	printStar(0, N - 1, N);//x좌표, y좌표, N값
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 2 * N - 1; j++) {
			cout << star[i][j];
		}
		cout << '\n';
	}
	return 0;
}