Study hard
(c++)백준 2448번: 별 찍기 - 11 본문
https://www.acmicpc.net/problem/2448
[풀이]
분할 정복을 사용하여 풀어야 한다.
배열 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;
}
'백준 > 분할 정복' 카테고리의 다른 글
(c++)백준 1517번: 버블 소트 (0) | 2020.07.01 |
---|---|
(c++)백준 2447번: 별 찍기 - 10 (0) | 2020.06.30 |
(c++)백준 1992번: 쿼드트리 (0) | 2020.06.30 |
(c++)백준 11729번: 하노이 탑 이동 순서 (0) | 2020.06.25 |
(c++)백준 1780번: 종이의 개수 (0) | 2020.06.25 |