2447 별찍기 -10

 

import java.util.Scanner;
 
public class Main {
    static int arr[][];
    public static void reculsive(int n, int w, int c) {
        if(c == 1){
            arr[n][w] = 1;
            return;
        }
            
        
        for(int i = 0; i <3; i++){
            for(int j = 0; j < 3; j++){
                int cc = c /3;
                int nn = n + cc*i;
                int ww = w + cc*j;
                if(i == 1 && j == 1)
                    continue;
                reculsive(nn,ww,cc);
            }
        }
        return;
    }    
    
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();
    StringBuilder sb = new StringBuilder();
    arr = new int [test][test];
    reculsive(0,0,test);
    for(int i = 0; i < test; i++){
        for(int j = 0; j <test; j++)
            if(arr[i][j] == 1)
                sb.append("*");
            else
                sb.append(" ");
        sb.append("\n");
    }
    System.out.println(sb);
    }
}
 

맨 처음에는 단순한 반복 노가다 문제인줄 알았다.

그러나 문제를 잘 읽어보니 Divide & Conquer 를 이용하는 재귀 문제였다.

그래서 코드를 싹 갈아엎고 다시 문제에 접근해봤더니, 재귀형식으로 들어가는

재귀 틀을 짜는 데만 30분 넘게 걸렸었던것 같다. 

그러고 나서 문제 제출을 하니 시간초과가 떴는데.

System.out.print가 너무 느려서 그렇다고 한다.

StringBuilder를 통해서 한번에 받아준뒤 출력했더니 성공하였다.