공부 자료/알고리즘
(C/C++) 백준 2448 - 별 찍기 11
뚜루뚜루세니
2021. 7. 21. 12:08
728x90
문제 출처: https://www.acmicpc.net/problem/2448
2448번: 별 찍기 - 11
첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)
www.acmicpc.net
1. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include <iostream>
#include <algorithm>
using namespace std;
//삼각형 높이 n, 삼각형 밑변 2n-1
char arr[3073][6244];
void star(int N, int x, int y) {
if (N == 3) { //높이가 3인 삼각형 = 최소 삼각형
//arr[높이][밑변]
//첫째줄
arr[y][x] = '*';
// 둘째줄
arr[y + 1][x - 1] = '*';
arr[y + 1][x + 1] = '*';
//셋째줄
for (int i = x - 2; i <= x + 2; i++) {
arr[y + 2][i] ='*';
}
return;
}
star(N/ 2, x, y); //위의 삼각형 높이, 꼭대기 좌표
star(N / 2, x - (N / 2), y + (N / 2)); // 왼쪽 아래 높이, 꼭대기 좌표
star(N / 2, x + (N / 2), y + (N / 2)); // 오른쪽 아래 높이, 꼭대기 좌표
}
int main() {
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++) { //높이
for (int j = 0; j < 2 * N - 1; j++) { //밑변
arr[i][j] = ' '; //배열 초기화
}
}
star(N, N-1, 0);//삼각형 높이, 삼각형 맨위 꼭짓점 좌표
for (int i = 0; i < N; i++) { //높이
for (int j = 0; j < 2 * N - 1; j++) { //밑변
printf("%c", arr[i][j]);
}
printf("\n");
}
}
|
cs |
2. 해결과정
재귀를 이용한 별찍기 문제이다. 규칙을 살펴보면 n=3일때 삼각형이 가장 작은 최소 삼각형이고,
n=6일때는 n=3일때 삼각형이 3개
n=12일때는 n=6일때 삼각형이 3개
n=24일때는 n=12일때 삼각형이 3개이다.
따라서 배열을 처음에 초기화를 시키고, star라는 재귀함수를 만들어서 삼각형의 높이, x좌표, y좌표를 제공한다.
삼각형을 쪼개면서 n==3이 되면 가장 작은 삼각형을 그리게끔 설정했다. arr[높이][밑변]이기 때문에 (y좌표,x좌표)로 생각해서 그려줘야한다. n!=3이면 계속해서 쪼개서 위의 삼각형, 왼쪽 아래 삼각형, 오른쪽 아래 삼각형으로 나눠서 또 재귀함수를 사용해서 결국 n==3일때까지 계속 쪼갠다는 것을 알 수 있다.
3. 느낀점
배열을 [높이][밑변]으로 해서 [y좌표][x좌표]로 생각을 해줬어야 했는데 아무 생각 없이 [x좌표][y좌표]로 놓고 출력을 시켰더니 원하는 모양이 나오지 않아 헤맸다. 별찍기 -10번 문제와 약간 유사한 느낌이여서 규칙을 찾는거는 생각보다 어렵지는 않았던 것 같다. 규칙보다 구현이 어려웠다..
728x90