[C++] 2447번 별 찍기 - 10 - 분할 정복, 재귀

1. 문제

• N이 3의 거듭제곱일 때, 크기 N의 패턴은 N*N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
• *** * * ***
• \(N>3\)일때 크기 N인 패턴은 공백으로 채워진 \((N/3) \times (N/3)\)정사각형을 크기 \(N/3\)의 패턴으로 둘러싸인 형태이다.

<입력>

• - 1 -   \(N(1 \leq N < 3^{8})\)

<출력>

• 별 출력

2. 재정의

• *** * * *** 프렉탈 출력

3. 해결 방법

• 크기가 3일 때 재귀 함수 종료
• f(N, x, y) : x, y를 시작점으로 하는 프렉탈 만들기

4. 실수한 점, 개선할 점

• 반복문을 사용하지 않음으로써 조건문 하나를 지울 수 있는데 이렇게 하면 소요 시간을 1/2로 줄일 수 있다.

 

<코드>

#include <iostream>

using namespace std;

const int MAX_N = 2188;

int N;
char starMap[MAX_N][MAX_N];

void drawStar(int size, int x, int y) {
    // 최소 크기 그림
    if(size == 3) {
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                if(i&1 && j&1)
                    continue;
                starMap[x+i][y+j] = '*';
            }
        }
        return;
    }
    
    // 프렉탈 구현
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            if(i&1 && j&1)
                continue;
            drawStar(size/3, x+size/3*i, y+size/3*j);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    
    drawStar(N, 1, 1);
    
    for(int i=1; i<=N; i++, cout << '\n')
        for(int j=1; j<=N; j++)
            cout << (starMap[i][j] == '*' ? '*':' ');
    
    return 0;
}

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.