[백준/C++/Gold(5)] 2447 - 별 찍기 - 10

2447번: 별 찍기 - 10

본인이 해당 문제의 출제자가 아니며, 문제 자체에 대한 모든 사항은 위의 링크가 출처임을 명시합니다.

 

[백준/C++/Gold(5)] 2447 - 별 찍기 - 10

 대체 뭘하면 흔한 별찍기 문제가 Gold 5씩이나 하는지 궁금해서 풀어보기로 했다.

 

문제 : 

3이 입력일 경우,

***
* *
***

9가 입력일 경우,

*********
* ** ** *
*********
***   ***
* *   * *
***   ***
*********
* ** ** *
*********

...

와 같은 재귀 문제이다.

(자세한 문제는 링크를 참조해주세요~ 완전히 베끼는 건 저작권에 문제가 있을 수 있으니...)

 

생각 : 

일단 이미 문제를 읽어보면 "재귀"란 말이 적혀있는 것을 보면, 흔한 Divide And Conquer 문제인 듯해서 그대로 풀기를 시도했다.

처음에는 3^7이 얼마인지 모르겠어서 계산했는데...

의외로 작네?

그래서 그냥 통으로 map을 잡아둔 뒤에 거기에 있는 내용을 프린트하기로 했다.

 

코드 (성공): 

#include <iostream>

using namespace std;

char map[2200][2200] = {0};

void recur(int n, int x, int y){
    if(n != 3){
        n /= 3;
        for(int a = 0; a < 3 * n; a += n){
            for(int b = 0; b < 3 * n; b += n){
                //cout << a << ':' << b << '\n';
                if(a == n && b == n) {
                    for(int c = x + a; c < x + a + n; c++){
                        for(int d = y + b; d < y + b + n; d++){
                            map[c][d] = ' ';
                        }
                    }
                } else {
                    recur(n, x + a, y + b);
                }
            }
        }
    } else {
        for(int a = 0; a < 3; a++){
            for(int b = 0; b < 3; b++){
                if(a == 1 && b == 1) {
                    map[x + a][y + b] = ' ';
                } else {
                    map[x + a][y + b] = '*';
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    recur(n, 0, 0);
    
    for(int i = 0; i < n; i++){
        cout << map[i] << '\n';
    }

    return 0;
}

바로 성공했다. 역시 그렇게 어렵지는 않았다.

recur 함수의 윗부분은 $n \gt 3$ 일 때 쓰는 함수이고, 이하의 재귀함수들과 중간에 비우는 공백을 출력하는 기능을 넣어두었다.

$n = 3$의 경우에는 위와 같지만 좀 간소화된 함수를 넣어두었다. 위에만 있어도 되게 만들 수 있지만, 사실 $n \eq 3$일 때의 기능을 먼저 만들고 본따서 위쪽의 기능을 만들었기 때문에 백업의 의미로써 남겨두었다.

 

확실히 dp문제에 비해서 D&Q가 훨씬 쉬운것 같다. dp는 silver 1인데 틀리고 gold 5인데 얘는 손쉽게 맞아버려서... 요즘 생각이 드는건데 그냥 어려운 알고리즘을 배우고 학습하는 것에 도전해서 더 어려운 문제를 푸는 것은 그렇게 나쁠 것 같지는 않다는 생각이다. 익숙해지면 좋으니까. 다음에는 아예 세그먼트 트리 / 레드 블랙 트리 / 다익스트라 같은 걸 다시 복습하는 건 어떤가 싶다.