star_11-2448

• 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;
}