[백준 BOJ 2447번] 별 찍기 - 10

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

2447번: 별 찍기 - 10

 

1. 문제

 

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

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

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

---

2. 입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

27

 

---

3. 출력

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

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

---

4. 풀이

이 문제 풀이에 앞서, 다양한 풀이가 있음을 인지하지 못한 채 문제에 적힌 내용을 인지하고 드는 생각 순서대로 풀이를 진행하였다.

 

먼저 이 문제를 풀이할 때 가진 생각은...

 

1. 문제에 주어진 규칙성을 찾고

2. 그 규칙들을 이용해서 귀납법 방식으로 작은 것부터 2-3개를 출력할 코드를 구현해보았다.

3. 그후, 그 사이에서 보이는 규칙을 가지고 n으로 일반화를 시도했다.

 

분명 재귀 알고리즘을 풀 때는 귀납법의 방식을 차용하여 그 규칙을 일반화시키는 것이 중요하다고 생각한다. 또한 '재귀'라는 특성을 이용하기 때문에 함수 안에 자기 자신 함수를 담을 때 넘겨줄 인자들이 어떻게 변해야하는지도 생각해보아야 한다.

 

이 문제를 풀이하자면...

먼저, N이라는 변의 크기를 입력받고 행,열의 크기가 N인 char형 배열을 생성하여 모두 *을 입력해두었다.

이후, N*N크기의 타일, (N/3)*(N/3)크기의 타일...3*3크기의 타일 순으로 비워야하는 부분들을 규칙을 이용하여 *을 제거해었다.

마지막으로, 1*1크기의 타일에 대해서는 제거할 *이 없으므로 이후 return 으로 정지시킨 후 출력을 진행해주었다.

---

5. 소스코드

import java.io.*;

class Main{
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        char [][] stars = new char [N][N];
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                stars[i][j] = '*';
            }
        }

        blanking(N, N, stars);
        
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                sb.append(stars[i][j]);
            }
            sb.append('\n');
        }

        System.out.println(sb);
    }

    public static void blanking(int M, int N, char [][] stars){
        
        if(M == 1) return;

        for(int i=M/3; i<N; i+=M){
            for(int j=M/3; j<N; j+=M){
                for(int k=0; k<M/3; k++){
                    for(int l=0; l<M/3; l++){
                        stars[i+k][j+l] = ' ';

                    }
                }
            }
        }

        blanking(M/3, N, stars);
    }
}

---

6. 배운 것

문제를 풀면서 내 코드에서 가장 마음에 들지 않은 부분은 4중 for문을 사용한 부분이다. 이로 인해 시간초과라는 문제를 지속적으로 생각하면서 풀이를 해야했고, 직접적 문제인 이 부분을 수정하지 못한 채, println -> StringBuilder, String -> char 등 다른 부분들을 수정해가며 메모리 사용 크기, 출력 시 메모리 사용 크기를 줄여 통과를 했다.

 

이후 다른 블로그 글들을 통해 다양한 문제 풀이를 발견했지만 내게 현재로서는 조금 접근하기 어려운 부분들이 있었다. 그런 생각을 하는 것이 어렵다고 느꼈지만 이 또한 여러 번 접근해보고 적용해본다면 익숙해질 것이다.

 

또한, 귀납법은 f(1), f(2), f(3), ..., f(n)의 순으로 가장 작은 부분들부터 적용을 하지만 실제로 재귀 알고리즘은 가장 바깥(n)부터 가장 안쪽 (1) 순으로 흐름이 이어진다. 이러한 부분을 고려할 필요가 있고, 큰 부분에서 작은 부분으로의 변화를 가장 먼저 주목해야겠다는 생각이 든다.