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

링크: https://www.acmicpc.net/problem/2447

 

문제

재귀적인 패턴으로 별을 찍어 보자. 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번째 줄까지 별을 출력한다.

 

---

풀이

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

(1,1), (1,2), ... (3,3)까지 총 9개의 점이 있을 때 가운데만 공백으로 처리하고 나머지는 별로 채우면 된다.

이를 재귀로 간단히 작성하면 다음과 같이 풀이를 작성할 수 있다.

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

bool answer[6562][6562];

void solve(int n, int y, int x){
    if (n == 3){
        answer[y][x] = true;
        answer[y][x+1] = true;
        answer[y][x+2] = true;
        answer[y+1][x] = true;
        // 가운데 빈 칸
        answer[y+1][x+2] = true;
        answer[y+2][x] = true;
        answer[y+2][x+1] = true;
        answer[y+2][x+2] = true;
    }
    else{
        solve(n/3, y, x);
        solve(n/3, y, x + (n/3));
        solve(n/3, y, x + (2*n/3));
        solve(n/3, y + (n/3), x);
        // 가운데 빈 칸
        solve(n/3, y + (n/3), x + (2*n/3));
        solve(n/3, y + (2*n/3), x);
        solve(n/3, y + (2*n/3), x + (n/3));
        solve(n/3, y + (2*n/3), x + (2*n/3));
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n;
    cin >> n;

    solve(n, 0, 0);

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (answer[i][j]){
                cout << "*";
            }
            else{
                cout << " ";
            }
        }
        cout << "\n";
    }
}

 

하지만 위 방법은 매우 많은 메모리를 차지한다. N은 최대 3^7 = 2187로 2187 * 2187 크기의 배열은 문제를 풀 때 충분히 여유롭지만 N의 거듭제곱이 더 커진다면 메모리가 충분하지 못할 것이다.

이를 해결하기 위해 배열에 값을 저장하지 않고 바로바로 계산하여 출력을 하도록 한 코드는 다음과 같다.

#include <iostream>
using namespace std;

void solve(int n, int y, int x){
    if ((y/n)%3 == 1 && (x/n)%3 == 1) {
        cout << " ";
    }
    else {
        if(n / 3 == 0)
            cout <<"*";
        else
            solve(n/3, y, x);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            solve(n, i, j);
        }
        cout << "\n";
    }
}

 

 

제출한 결과는 다음과 같은데 위가 배열에 값을 저장한 첫 번째 풀이, 아래가 두 번째 풀이이다.

확실히 각각 시간과 메모리에서 장점을 보이는 것을 확인할 수 있다.