[백준] 2447번 별 찍기 - 10

문제: 2447번: 별 찍기 - 10

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

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 == 0) {
        board[x][y] = '*'; // 별로 채우기
        return;
    }

    int third = n / 3;
    // 맨 가운데는 Fiil 안해줄것
    Fill(third, x, y, board);
    Fill(third, x, y + third, board);
    Fill(third, x, y + 2 * third, board);
    Fill(third, x + third, y, board);
    Fill(third, x + 2 * third, y, board);
    Fill(third, x + third, y + 2 * third, board);
    Fill(third, x + 2 * third, y + third, board);
    Fill(third, x + 2 * third, y + 2 * third, 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>(n);

        for (int j = 0; j < n; j++) {
            board[i][j] = ' ';
        }
    }
    Fill(n, 0, 0, board);

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


    return 0;
}

 

이제 어느 정도는 재귀 문제에 감을 잡은 것 같다. 

 

처음에는 벡터 안 쓰고 어떻게 할 수 있을지 고민하다가 그냥 쓰는게 정신 건강에 좋을 것 같아서 벡터를 이용했다.

 

재귀를 돌릴 때 구간을 나눠서 생각을 했다. 일단 가운데만 공백이고 나머지는 * 이 출력되어야 하므로 재귀를 돌릴 때 가운데만 빼고 돌렸다.

 

즉, 각 단계에서 밑의 단계로 내려갈 때 맨 중앙은 Fill 메서드를 호출하지 않았다. 그리고 n 의 값이 0일 때 * 을 board 에 저장하도록 했다.

 

마지막에 board 에 저장해놓은 것을 차례대로 출력하면 된다.

 

 

 

참고자료:

[바킹독의 실전 알고리즘] 0x0B강 - 재귀