[boj] 백준 2447 별 찍기 10 (c++) - 재귀

[문제]

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

2447번: 별 찍기 - 10

 

[풀이]

 

n x n 사각형에 대해 가운데 부분이 공백으로 이루어지는 형태가 반복된다는 것을 알 수 있다. 따라서 이 때 어떤 좌표값이 공백이 되는지를 일반화해야 한다.

 

n이 3이면, (1, 1), (1, 4), (1, 7), (4, 1), (4, 4), (4, 7) 등의 좌표가 공백이 된다. 

→ ( i / 1 ) % 3 == 1 && ( j / 1 ) % 3 == 1

 

n이 9이면, (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5) 등의 좌표가 공백이 된다.

→ ( i / 3 ) % 3 == 1 &&  ( j / 3 ) % 3 == 1

 

즉, ( i / ( n / 3 ) ) % 3 ==1 &&( j / ( n / 3 ) ) % 3 ==1 의 좌표값이 공백임을 일반화하여 나타낼 수 있다.

 

(i,j)의 값이 공백이라면 공백을 출력하고, 아니라면 n/3으로 크기를 줄여 재귀적으로 다시 탐색한다. n이 1로 줄여진 경우, 더이상 탐색이 불가능하므로 "*"를 출력한다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

void star(int i, int j, int n){

    if (n == 1){
        cout << "*";
    }
    else if ((i / (n/3)) % 3 == 1 && (j / (n/3)) % 3 == 1){
        cout << " ";
    }
    else{
        star(i, j, n/3);
    }
}

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

    int n;
    cin >> n;

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

}