[백준] 2448번 별 찍기 - 11

문제: 2448번: 별 찍기 - 11

basic-algo-lecture/workbook/0x0B.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

void Fill(int n, int x, int y, vector<vector<char>>& board) {
    if (n == 3) {
        // n 이 3 이면 작은 삼각형 board 에 저장
        board[y][x] = '*';
        board[y + 1][x - 1] = '*';
        board[y + 1][x + 1] = '*';
        for (int i = -2; i <= 2; i++)
            board[y + 2][x + i] = '*';

        return;
    }

    int nextN = n / 2;
    // n 이 3이 아니면 계속 밑으로..
    Fill(nextN, x, y, board);
    Fill(nextN, x - nextN, y + nextN, board);
    Fill(nextN, x + nextN, y + nextN, board);
}


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

    int n;
    cin >> n;
    vector<vector<char>> board(n);
    for (int i = 0; i < n; i++) {
        board[i] = vector<char>(2 * n);

        for (int j = 0; j < 2 * n; j++)
            board[i][j] = ' ';
    }

    int mid = n - 1; // x 축 값
    Fill(n, mid, 0, board);

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

    return 0;
}

 

음.. 규칙만 잘 찾으면 풀 수 있는 문제다. 사실 규칙 찾는 게 조금 어려웠다.

 

맨 처음에 Fill 메서드를 호출할 때 x, y 값으로 무슨 값을 줘야 하는지 고민했는데 세 개의 삼각형 중 맨 위 삼각형의 맨 위 꼭짓점의 값을 주면 되는 거였다.

 

y 값은 당연히 0 이고 x 의 값이 중요했는데 문제 예시를 살펴보니 x 의 값은 n 값에 - 1을 한 값을 주면 되는 것이었다. n-1 값이 맨위 삼각형의 맨 위 꼭짓점의 x 위치랑 같다.

 

Fill 에 진입하면 n 값이 3일 때 board 값을 정해주고, 아니라면 Fill 을 호출하면 된다. 현재 단계에서 아래 단계로 갈 때 세 개의 삼각형으로 나눠지므로, 각 삼각형의 맨 위 꼭짓점의 값을 매개변수 값으로 넘겨주면 된다.

 

각 삼각형의 맨 위 꼭짓점의 값은 현재 단계의 x, y 값에 현재 n 값을 / 2 한 값을 더하거나 빼서 구할 수 있다.

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x0B강 - 재귀

[실전 알고리즘] 0x0B강 - 재귀