[백준 2448] 별 찍기 - 11

🔗 알고리즘 문제

24일 알고리즘 스터디를 진행하며 친구가 풀이해준 문제이다. 평소 약하다고 생각하는 재귀 문제이지만, 친구의 풀이를 듣고 내가 직접 풀어보니 쉽게 해결할 수 있었다.

문제 분석

여느 별 찍기 문제와 같이 예제를 보고 규칙을 찾아 규칙대로 별을 찍으면 되는 문제이다.

발상 & 알고리즘 설계

이 문제의 규칙은 n(높이)가 3이 될 때까지 한 개의 중심점에서 n / 2의 만큼 떨어진 새로운 중심점을 찾아내고 n이 3이 되면 삼각형을 그려주어 최종적으로 모든 삼각형이 그려지게 하면 된다.

위와 같이 재귀 형식으로 새로운 중심점을 찾아주고 높이가 3이 됬을 때 각각의 위치에서 삼각형을 그려주면 된다!

코드

#include<iostream>
#include<cstring>

using namespace std;

char map[3600][6200] = {};

void makeTriangle(int i, int j){
    map[i][j + 2] = '*';
    map[i + 1][j + 1] = '*';
    map[i + 1][j + 3] = '*';
    for(int v = 0; v < 5; v++)
        map[i + 2][j + v] = '*';
}

void star(int i, int j, int n){
    if(n == 3){
        makeTriangle(i, j);
        return;
    }

    star(i, j, n / 2);
    star(i + n / 2, j - n / 2, n / 2);
    star(i + n / 2, j + n / 2, n / 2);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n;

    cin >> n;

    memset(map, ' ', sizeof(map));
    star(0, n - 3, n);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n * 2; j++){
            cout << map[i][j];
        }
        cout << "\n";
    }
}