C++ / 백준 / 2448 / 별 찍기 - 11

문제

https://www.acmicpc.net/problem/2448

2448번: 별 찍기 - 11

문제풀이

 

N=3일 때 모양이다.

N이 몇이든 이 모양이 기본이 되는 문제이다.

Nx(N*2-1) 행렬이다.

N=3일 때 y=0, x=3-1인 부분이 기준점이 되므로

[y][x] = *, [y+1][x-1], [y+1][x+1] = *, [y+1][x-2] ~ [y+1][x+2] = *이라는 기본 형태를 잡아준다.

N=6일 때 모양이다.

Nx(N*2-1) 행렬이다.

기준점이 (0, N-1)이고, 또 다른 점은 (0+3, N-4), (0+3, N+4)이다.

N=12일 때 모양이다.

기준점이 9개가 있다.

이 예제를 보면 재귀를 이용해서 각각 기준점을 잡아주고, 기준점일 때 해당 좌표에 기본 형태를 넣어주면 된다.

함수에 N, 0, N-1을 집어넣어 맨 윗줄 기준점을 잡고, N/2를 하여 (0+6, 11-6=5), (0+6, 11+6=17) 두 기준점과, (0, 11) 기준점을 다시 잡는다.

이 그림에서 함수를 실행하면 빨간 부분을 처음에 잡고, (0, 11) 기준점을 다시 잡아 그다음 기준점인 주황 부분을 잡는다.

더 이상 잡을 기준이 없을 때 N=3일 때, 저 형태를 벡터에 집어넣는다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

vector<vector<char>>star;
void Make_Star(int N, int y, int x) {
    if (N == 3) {
        star[y][x] = '*';
        star[y + 1][x - 1] = star[y + 1][x + 1] = '*';
        for (int idx = 0; idx < 5; ++idx)
            star[y + 2][x - 2 + idx] = '*';
    }
    else {
        Make_Star(N / 2, y, x);
        Make_Star(N / 2, y + N / 2, x - N / 2);
        Make_Star(N / 2, y + N / 2, x + N / 2);
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N = 0;
    int y = 0, x = 0;
    cin >> N;

    star = vector<vector<char>>(N, vector<char>(N * 2 - 1, ' '));

    Make_Star(N, 0, N - 1);

    for (y = 0; y < N; ++y) {
        for (x = 0; x < N * 2 - 1; ++x) {
            cout << star[y][x];
        }
        cout << '\n';
    }
}