2447번: 별 찍기 - 10 (BOJ C/C++)

2447번: 별 찍기 - 10

사용 언어: C++

 

문제

재귀적인 패턴으로 별을 찍어 보자. 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

보드를 전부 ' '로 채우고 이전에 푼 재귀 문제들과 마찬가지로 n에 따라 나눠진 구역에 x와 y도 그에 상응하는 n의 값으로 바꾸고 (ex: func(n/3, x+ n/3*i, y+n/3*j) n==1인 base 조건일때 보드가 * 이므로 별을 넣어주고 나중에 전체 출력을 하면 답이 나오는 풀이다.

#include <bits/stdc++.h>
using namespace std;

char board[2190][2190];

void func(int n, int x, int y){
    if(n==1){
        board[x][y] = '*';
        return;
    }

    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(i==1 && j==1)
                continue;
            func(n/3, x + n/3*i, y + n/3*j);
        }
    }
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    for(int i=0; i<N; i++)
        fill(board[i], board[i]+N, ' ');
    func(N,0,0);
    for(int i=0; i<N; i++)
        cout << board[i] << '\n';

    return 0;
}

 

풀이 2

풀이 1과 달리 재귀를 돌리면서 공백과 별을 출력하는 풀이다. 풀이 1과 달리 func을 많이 호출해서 메모리는 적게 사용하는 대신 시간은 조금 더 걸린다.

#include <bits/stdc++.h>
using namespace std;

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

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++)
            func(N,i,j);
        cout<< '\n';
    }

    return 0;
}