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

 

🧫 문제 분석

 

✔️ 출처

별 찍기 골드 5

 

📖 문제

 

분할정복 문제로

N이 3의 거듭 제곱으로 주어지고 

3의 거듭 제곱을 3으로 나눌때 중앙이 공백이 되어야한다.

 

재귀로 주어진 N / 3 을 하여 3등분을 하고 (이에 따라 N/3 개의 위치가 생김)

각 위치에 따라 재귀로 호출한 후

재귀가 끝나면 각 구역의 가운데 부분을 for문을 돌면서 빈칸을 채운다. 

 

예를 들어 27이면

y : 0, 9, 18 

x : 0 , 9, 18 

 

이런 식으로 3등분 했을 때 구역의 첫 위치를 재귀로 넘긴다. 

 

 

나는 먼저 배열을 *로 가득 채운 상태에서 

공백을 넣는 방법을 사용하였다. 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {
    static char[][] stars;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        stars = new char[n][n];

        for (char[] star : stars) {
            Arrays.fill(star, '*');
        }

        recursion(0, 0, n, n);

        for (char[] star : stars) {
            sb.append(star).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void recursion(int r, int c, int length, int n) {

        // 1일 때는 넘김, 3이상 부터 가운데를 for문으로 처리할 예정
        if (length == 1) {
            return;
        }

        int div = length / 3;
        
        for (int i = r; i < r + length; i += div) {
            for (int j = c; j < c + length; j += div) {
                recursion(i,j, div, n); // 3등분으로 분할하여 재귀
            }
        }

        // 가운데 빈칸 넣기
        for (int i = r + div; i < r + div + div; i++) {
            for (int j = c + div; j < c + div + div; j++) {
                stars[i][j] = ' ';
            }
        }
    }
}

 

🔅 다른 사람 풀이를 배워서 풀이

import java.io.*;
import java.util.*;

public class Main {
    static char[][] stars;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        stars = new char[n][n];

        recursion(0,0,n,true);

        for (char[] star : stars) {
            sb.append(star).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void recursion(int r, int c, int length, boolean isStar) {
        // 길이가 1이고 별이 있다면 별 처리
        if (length == 1 && isStar) {
            stars[r][c] = '*';
            return;
        }

        int div = length / 3;

        // 별이 있는 구간이고 길이가 3이상이면 구간 더 나누기 
        if (isStar) {
            int count = 1;
            for (int i = r; i < r + length; i += div) {
                for (int j = c; j < c + length; j += div) {

                    // 가운데 빈 공간
                    if (count == 5) {
                        recursion(i, j, div, false);
                        count++;
                    } else {
                        recursion(i, j, div, true);
                        count++;
                    }
                }
            }
            // 별이 없는 구간은 빠르게 전부 공백 처리 
        } else {
            for (int i = r; i < r + length; i++) {
                for (int j = c; j < c + length; j++) {
                    stars[i][j] = ' ';
                }
            }
        }
    }
}

 

❗ 오답노트 / 필요한 지식

1.  다른 사람들 풀이를 봤는데 빈 배열에 별을 찍는 방법을 더 많이 쓴다. 아무래도 별을 미리 찍으면 그 만큼 시간이 사용되서 그런거 같다. 
2. 다른 사람 풀이대로 풀어보고 이해해보자. 24.9.5 일 다시 풀어보고 이해완
3. for문에서 반복 제한으로 r + length 를 해야하는데 length만 해서 앞부분만 빈칸이 생겼었는데 정말 부끄럽다.. 이런 실수를 하다니..ㅠㅠ  기억하자.. 분할 정복을 하면 끝 위치를 지정해주자.