[백준] 2447번 별 찍기 10 - 재귀(3), 분할정복(1) [JAVA]

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

2447번: 별 찍기 - 10

---

     문제

// 입력
27

// 출력
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

     문제 풀이

• 분할 정복(Divide and Conquer) 와 재귀 함수 문제이다.
• 분할 정복이란?
  Divide and Conquer , 그대로 해결할 수 없는 문제를 작은 문제로 나누어(Divide) 해결하는 방법, 알고리즘이다.
• 푼 방법
  1) 별을 그릴 2차원 배열 arr[][]를 선언한다.
  2) 분할을 어떻게 해서 문제를 풀어야하는가?
  힌트1) 크기 3의 경우, 패턴을 생각해보자. [0][0], [0][1], [0][2], [1][0], [1][1] ... 의 순서로 1,2,3,4,5, ... 를 한다면 blank가 되는 칸은 5번째 칸이다. 이걸 확장하여서 생각해야 된다.
  힌트2) 크기가 3ⁿ인 경우, 패턴을 생각해보자. [0][3ⁿ⁻¹] , [0][2 * 3ⁿ⁻¹], [0][3ⁿ], ... 의 순서로 1,2,3,4,5... 를 한다면 blank가 되는 칸은 5번째 칸이다.
  3) 힌트1)과 힌트2)를 합쳐서 생각해보자.
  힌트2)의 3ⁿ을 3으로 계속 나누어갈 경우, 1이 되는 순간이 존재한다. 즉, 재귀를 했을 때, base case가 되는 경우가 존재한다.
  4) 크기가 3ⁿ인 경우는 너무 크다. 1,2,3,4,5,... 구역을 나누고 (Divide), 그 구역을 다시 나누고(Recursion)를 반복하면 결국 base case에 도달할 수 있고, base case는 '*'를 리턴하면 된다.

다음과 같이 구역을 나눈다.

3씩 나누어 구역을 나누는 재귀 문제다.

큰 문제를 작은 문제로 분할하는 방식 Divide

---

        JAVA code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class baekjoon2447 {
    static void star(char[][] arr, int x, int y, int N, boolean blank) {
        // 공백칸 일 경우
        if (blank) {
            for (int i = x; i < x + N; i++) {
                for (int j = y; j < y + N; j++) {
                    arr[i][j] = ' ';
                }
            }
            return;
        }
        if (N == 1) {
            arr[x][y] = '*';
            return;
        }

        int size = N / 3;
        int count = 0;
        // x와 y를 size만큼 더하는게 포인트
        for (int i = x; i < x + N; i += size) {
            for (int j = y; j < y + N; j += size) {
                count++; // 다섯번째 구역을 판별하기 위해서
                // 재귀
                if (count == 5) {
                    star(arr, i, j, size, true);
                } else {
                    star(arr, i, j, size, false);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        char[][] arr = new char[N][N];

        star(arr, 0, 0, N, false);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(arr[i][j]);
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }
}

---

정리

https://st-lab.tistory.com/95?category=852877 를 보면서 이해했고, 사진의 출처도 여기입니다.

[백준] 2447번 : 별 찍기 - 10 - JAVA [자바]

Divide And Conquer의 첫 풀이라 감이 오지 않아, 블로그를 정말 많이 참고하였다.
매우매우 설명이 잘되어있으니 제 정리글로 감이 오지 않는다면 꼭 한번 보길 바란다.