PS/백준

백준 / Recursion(재귀) / 2447번 / 별 찍기 - 10 / C++

KimMinJun 2020. 9. 28. 09:19

문제

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

27

예제 출력 1

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

 

#include <iostream>
using namespace std;

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

int main() {
    int k;
    cin >> k;
    
    for(int i=0; i<k; i++) {
        for(int j=0; j<k; j++) {
            star(i,j,k);
        }
        cout << endl;
    }
}

이 문제는 혼자 해결하지 못해 구글링의 힘을 빌렸다.

 

일단 k가 3일때 생각해보자.

빈칸이 생기는 것은 i,j가 1일때이다.

star(1,1,3)을 보면, 첫번째 if문은 충족하지 않는다. (i/k)%3=0이기 때문이다(j도 마찬가지)

그럼 else문으로 간다.

k/3=1 이므로 else안의 if문 역시 충족하지 않는다.

그럼 else의 재귀를 통해 star(1,1,1)이 된다.

그럼 다시 맨위의 if를 보면 (1/1)%3 = 1이 되므로(j 동일) 빈칸을 출력하게 된다.

9, 27 ,81 ... 똑같은 방식이다.