- toc {:toc}
📦2448: 별찍기 11
[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-17
문제 확인하기
풀이
- 분할 정복으로 풀이했다. 입력이
로 주어지고, 이미지는 반복적인 구조를 띤다. - 그림은 24가 주어진 그림인데, 높이는 24, 밑변은 47이다.
- 즉, 높이 =
, 밑변 = 이다.
- 즉, 높이 =
- 큰 삼각형을 작은 삼각형 3개로 나누면 높이가 12, 밑변은 23이 된다.
- 또 3개로 나누면 N=6 일 때가 된다.
- (y, x) = (0, 0) 이라 가정하고 N=24인 그림에서 N=12로 쪼갤 때 3개의 별삼각형의 시작점을 구해서 재귀적으로 풀면 된다.
#include <iostream>
#define endl '\n'
using namespace std;
int N;
char tri[3][6] = {
" * ",
" * * ",
"*****"
};
char board[3100][6200];
void Input(){
cin >> N;
}
void Solution(int n, int y, int x){
if(n == 1){
for(int i=0; i<3; i++){
for(int j=0; j<5; j++){
board[y+i][x+j] = tri[i][j];
}
}
return;
}
Solution(n/2, y, x+3*n/2);
Solution(n/2, y+3*n/2, x);
Solution(n/2, y+3*n/2, x+3*n);
}
void Solve(){
for(int i=0; i<N; i++){
for(int j=0; j<2*N-1; j++){
if(board[i][j] != '*') cout << " ";
else cout << "*";
}
cout << endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
Input();
Solution(N/3, 0, 0);
Solve();
return 0;
}