[java 백준]골드 4/2448번 별 찍기 -11

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

2448번: 별 찍기 - 11

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static int n;
    public static char[][] arr;
    public static StringBuilder sb;
 
    public static void printStar(int row, int col, int num) {
 
        if (num == 3) {
            // 다 쪼개줌, 재귀 끝 --> 별 찍어주기
            // 중간지점을 기준으로 별을 찍을 것 --> 공백은 신경쓰지않아도 됨 어차피
            // 처음에 공백으로 초기화 시켜줌
            arr[row][col] = '*';
            arr[row + 1][col + 1] = arr[row + 1][col - 1] = '*';
            arr[row + 2][col - 2] = arr[row + 2][col
                    - 1] = arr[row + 2][col] = arr[row + 2][col + 1] = arr[row + 2][col + 2] = '*';
            return;
        } else {
            int n = num / 2;
            // 계속 3등분씩 잘라줄 것
            // 1행
            printStar(row, col, n);
            // 2행
            printStar(row + (num / 2), col + (num / 2), n);
            // 3행
            printStar(row + (num / 2), col - (num / 2), n);
        }
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int num = n * 2 - 1;
        sb = new StringBuilder();
        arr = new char[n][num];
 
        // 공백으로 채워넣기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < num; j++) {
                arr[i][j] = ' ';
            }
        }
 
        printStar(0, n - 1, n);// 왜 n-1
        // 그래야 딱 정중앙에 별이 찍힘 n-1이 딱 열의 중간지점
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < num; j++) {
                sb.append(arr[i][j]);
            }
            sb.append('\n');
        }
 
        System.out.println(sb);
 
    }
 
}

이 문제도 기존의 분할정복과 비슷하게 풀면되는데, 난 항상 먼저 파악해야하는 규칙을 계속 놓쳤다.

바로 큰 덩어리에서 -> 가장 작은 덩어리(기준이 되는 덩어리)으로 가는데 어떠한 일정한 비율로 나눠지는지에 대한 생각을 하지 않았다.

(그냥 그림을 보고 어렵다.. 이 생각만 했을뿐..ㅎ ) 

지금까지 계속 분할정복 문제를 풀때 특히 그림이 첨부된 문제들은 항상 2로 나눠진다는지, 3으로 나눠진다는지의 규칙이 있었다

이 문제도 똑같다. 하지만 차이점이 있다면 도형이 나눠지는 비율과 숫자 n이 나뉘는 비율이 다르다는 것이다. (왜냐면 행이랑 열이 다르기때문, 이전까지 문제들은 행과 열이 같아서 도형이 나눠지는 비율이랑 숫자 n이 나눠지는 비율이 같았음) 얘는 도형 자체는 계속 3으로 나눠진다.

 

기준이 되는 3줄짜리 작은 덩어리가 될때까지 나눠주면된다.

그리고 n은 3*2^k이기 때문에 24->12->6->3으로 2씩 나눠진다. 

즉 n이 3이 될때까지 도형을 계속 나눠주고(재귀) , 3이 되면 별을 출력해주면된다. 

 

처음에 도형을 3등분 시켰을 땐 

위의 사진 처럼 자를 수 있다. 이때 n은 12이다

중간 ,좌측 ,우측 으로 총 3등분해서 잘라낼 수 있다. 

 

다시 잘라진 애들을 또 3등분 하면 아래 그림처럼 된다. (그림이 좀 더럽다 ㅜㅜ)

이때는 n이 6이다.

 

다시 한번 3등분씩 나눠서 n이 3이 될때는 가장 작은 덩어리인 기준이 되는 삼각형이 되기 때문에 이때는 출력해주면된다.

재귀(분할하는 거)가 끝나고 별을 출력하는 코드는

if(num==3){
    arr[row][col]='*';
    arr[row+1][col-1]=arr[row+1][col+1]='*';
    arr[row+2][col-2]=arr[row+2][col-1]=arr[row+2][col]
    =arr[row+2][col+1]=arr[row+2][col+2]='*';
}

위 사진을 코드로 구현했다고 보면된다.

중간을 기준으로 앞 뒤로 찍어줄 수 있게 만들었다.

나는 처음에 별을 찍는 기준을 어디로 해줘야할지 굉장히 난감했는데 어차피 공백으로 처음에 채워줬으니까 맨 위 중간을 기준으로 해도 상관없었고, 이 문제에서 맨 위 중간의 역할이 매우 컸다. 

 

그러면 분할하는 코드는

 

else{
    int div=num/2; //N은 2만큼씩 나눠짐(혹은 행이 2만큼씩 나눠짐)
    printStar(row,col,div);
    printStar(row+div,col-div,div);//좌측
    printStar(row+div,col+div,div);//우측 
}

 

 

계속 중간,좌측,우측으로 계속 3등분되기때문에 중간/좌측/우측 총 3줄만 써주면된다.

그리고 row,col을 써주는 것의 기준은 각 삼각형이 맨 위 맨 중간이다. 이게 내가 앞에서 맨 위 중간이 역할이 크다는 것의 이유이다. 맨 위 중간을 기준으로 더 작은 삼각형으로 계속 분할해주기 때문이다.