[BOJ-2447][C++] 별 찍기 - 10

문제

재귀적인 패턴으로 별을 찍어 보자. 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=3^k$이며, 이때 $1 ≤ k < 8$이다.

 

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

예제 입력 1 

27

 

예제 출력 1 

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

 

알고리즘 분류

• 분할 정복
• 재귀

 

문제 출처

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

2447번: 별 찍기 - 10

 

---

 

문제 해결 방법

• 위의 문제는 프랙탈(Fractal) 도형 문제와 연관이 있다.

프랙탈 도형의 예

• 프랙탈 도형 문제는 보통 분할 정복(Divide and Conquer) 기법을 이용하여 해결할 수 있다.

 

기본 패턴 분석하기

***
* *
***

• N = 3일 때 나타나는 기본적인 패턴을 좌표계를 이용하여 분석해본다.

	0	1	2
0	*	*	*
1	*		*
2	*	*	*

• 비어 있는 부분의 좌표는 (1, 1)로 표현할 수 있다.
• 다음과 같은 경우에는 비어 있는 좌표는 (1, 1), (4, 1), (7, 1)로 표현할 수 있다.

	0	1	2	3	4	5	6	7	8
0	*	*	*	*	*	*	*	*	*
1	*		*	*		*	*		*
2	*	*	*	*	*	*	*	*	*

• 따라서 가장 기본적인 패턴을 만족시키기 위한 조건은 다음과 같다.

i % 3 == 1 && j % 3 == 1

 

응용 하기

• N = 9일 때 나타나는 패턴을 분석해본다.

		0			1			2
		0	1	2	3	4	5	6	7	8
0	0	*	*	*	*	*	*	*	*	*
	1	*		*		*		*		*
	2	*	*	*	*	*	*	*	*	*
1	3	*	*	*				*	*	*
	4	*		*				*		*
	5	*	*	*				*	*	*
2	6	*	*	*	*	*	*	*	*	*
	7	*		*	*		*	*		*
	8	*	*	*	*	*	*	*	*	*

• N = 3일 때의 기본 패턴의 크기가 커진 형태를 띄는 것을 확인할 수 있다.
• 가운데 부분의 비어있는 좌표는 (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

 

 알고리즘 작성하기

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

 

코드

#include <iostream>
using namespace std;

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

int N;

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

    cin >> N;

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

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [재귀]
• 골드V