백준 2447] C++ 별 찍기 - 10

 

 

 

 

 

 

 

해당 문제는 백준 사이트에서 풀 수 있습니다.

 

www.acmicpc.net/problem/2447

 

1. 문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

 

***

* *

***

 

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

 

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

 

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

2. 조건

1. 숫자 N이 주어진다.

2. 해당 숫자는 3의 배수로 주어지며 N * N의 배열을 선언해야 한다.

3. 별을 찍어야 하는데 3의 배수당 중앙 점을 지운 상태로 출력해야 한다.

 

 

3. 풀이

해당 풀이는 우선 차근차근 생각해보면 됩니다.

 

우선 3 * 3 형태의 배열일 경우 가운데를 비워야하니

 

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        if (i == 1 && j == 1)
            cout << ' ';
        else
            cout << '*';
    }
    cout << endl;
}

이런식으로 만들어야 할 것입니다.

 

즉, ( i == 1 && j == 1 ) 인 경우엔 공백이 출력되게끔 해야죠.

해당 조건을 재귀를 통해 반복시키면 되는데, 2차원 배열의 재귀 이므로 높이를 설정해 줘야 합니다.

높이 관련된 부분은 색종이 만들기(www.acmicpc.net/problem/2630) 문제와 흡사합니다.

 

단지, 재귀일 때 조건문에 무엇을 걸어야 할지 찾아내는게 여간 쉬운게 아닙니다.

저도 고민하다가 도저히 답이 안나와서 인터넷을 찾아 참고해서 풀었습니다.

 

코드를 보시면서 이해하는걸 추천드립니다.

 

4. 코드

#include <iostream>
#include <vector>
#include <algorithm>

#pragma warning(disable: 4996)

using namespace std;

void star_init(vector<vector<char>>& v, int x, int y, int h) {
    if (h == 1) {
        v[x][y] = '*';
        return;
    }

    int div = h / 3;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {

            if (i == 1 && j == 1) continue;
            star_init(v, x + i * div, y + j * div, div);
        }
    }
}

int main() {
    int T;
    int N, M, K, H;
    int X, Y;
    
    cin >> N;
    vector<vector<char>> v(N, vector<char>(N, ' '));

    star_init(v, 0, 0, N);

    for (auto& e : v) {
        for (auto c : e) {
            cout << c;
        }
        cout << endl;
    }

    return 0;
}