백준/분할 정복
(c++)백준 2448번: 별 찍기 - 11
Nimgnoej
2020. 6. 30. 14:48
https://www.acmicpc.net/problem/2448
2448번: 별 찍기 - 11
첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (k ≤ 10)
www.acmicpc.net


[풀이]
분할 정복을 사용하여 풀어야 한다.
배열 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;
}