[Boj_2447] 별 찍기 - 10

📎 문제 링크

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

2447번: 별 찍기 - 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=3k이며, 이때 1 ≤ k < 8이다.

 

▸ 출력

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

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 5
• 🔔  문제 유형 : 분할 정복, 재귀
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

먼저 주어지는 수는 3의 거듭제곱의 수이고,

n = 3일 때의 모양은 다음과 같다.

*	*	*
*		*
*	*	*

이 모양은 *을 연속적으로 채우면서 진행되는데

이때, 한 블록의 가운데는 채워지지 않는다.

 

예시를 보자면

n = 3일 때, 

*	*	*
*		*
*	*	*

 

n = 9 일 때, 

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

 

n = 27 일 때는 아래와 같다.

 

즉, n이 3의 제곱수일 때, 아래와 같은 그림으로 나타낼 수 있다.

 

이때 찾을 수 있는 규칙은 한 블록에서 가운데 부분은 공백이라는 것이다.

 

n = 3일 때 2차원 배열을 생각해 보면, 공백은 (1, 1)이다.

즉, 행을 채울 때, (0, 0), (0, 1), (0, 2), (1, 0)까지는 별을 출력하고

별 출력이 4번 이루어지면 그다음 블록은 반드시 공백이다.

 

마찬가지로, n = 9라면 n = 3일 때의 모양이 한 블록이 되어 반복된다.

 

위와 같은 방법으로 문제를 풀어보자면

먼저, n = 27일 때, 9개의 블록을 구분할 수 있다.

이때 공백인 구간을 만족한다면 그 구간은 공백으로 채우고, 공백이 아닌 구간은 재귀호출을 한다.

 

n = 9로 넘어간다면 이 전과 같이 다시 9개의 블록으로 나뉜 뒤,

공백 구간은 공백으로 채우고, 아닌 구간은 다시 재귀 호출을 한다.

 

그렇게 된다면 n = 3일 때로 갈 것이고,

위와 같은 과정을 반복하다 보면 n = 1일 때가 온다.

여기서 더 쪼개지 못하기 때문에 해당 구역의 배열을 공백 또는 별로 채우면 된다.

 

즉, 각 단계에서 9개의 블록으로 구분한 뒤, 좌표에 따라 공백 또는 재귀 호출을 반복해 주며 더 이상 나눌 칸이 없을 때까지 반복하는 것이다.

 

규칙 찾기부터 구현까지 굉장히 어려웠던 문제였다 😭😂

 

✔ 최종 코드

메모리 : 22428KB
시간 : 216ms

import java.io.*;

public class Main {
    static int n;
    static char[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine()); // 3의 거듭제곱, nxn
        arr = new char[n][n]; // 별을 그릴 이차원 배열
        partition(0, 0, n, false); // 시작점, 공백칸 여부
        // 출력
        for (char[] line : arr) {
            bw.write(line);
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static void partition(int x, int y, int size, boolean blank) {
        if (blank) { // 공백 칸이라면
            for (int i = x; i < x+size; i++) {
                for (int j = y; j < y+size; j++) {
                    arr[i][j] = ' ';
                }
            }
            return;
        }

        // 더 이상 쪼갤 수 없을때
        if (size == 1) {
            arr[x][y] = '*';
            return;
        }

        int newSize = size/3; // 한 블록의 사이즈
        int cnt = 0;
        for (int i = x; i < x+size; i+=newSize) {
            for (int j = y; j < y+size; j+=newSize) {
                cnt++;
                // 공백 칸일 경우
                if (cnt == 5) partition(i, j, newSize, true);
                else partition(i, j, newSize, false);
            }
        }
    }
}

 

 

📍 함께 풀어보면 좋은 백준 문제

• 색종이 만들기
• 쿼드트리
• Z

 

 

📃 reference

• https://st-lab.tistory.com/95