백준 2447번 별찍기-10(Java)

재귀를 이용한 별찍기다. 2시간정도 낑낑거리면서 풀었다. 누구나 규칙을 찾을수 있지만, 그것을 알고리즘으로 구현하는게 어려운 문제다.

일단 밑의 코드로 실행을 시키면 실행은 된다만, 시간초과가 뜬다. 3^6(729) 입력시 걸리는 시간이 1초가 넘어간다. 문제에서는 3^7 까지가 조건이니 시간초과.

 

풀이방법

 

*	*	*
*		*
*	*	*

크기가 3인 패턴은 가운데 하나만 비어있는 패턴이다. 

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

크기가 9인 패턴을 보자. 규칙성이 보인다. 크기가 3인 패턴과 같은 규칙이다. 다른점은 *이 들어갈 자리에 크기가 3인 패턴이 들어갔다는 것이다.

 

크기가 27인 패턴 역시 *이 들어갈 자리에 크기가 9인 패턴이 들어가있다.

규칙성을 알았으니 이를 식으로 구현해보자.

0,0	0,1	0,2
1,0	1,1	1,2
2,0	2,1	2,2

크기가 3인 패턴일때, 비어야 할 곳은 1,1이다.

			3,3	3,4	3,5
			4,3	4,4	4,5
			5,3	5,4	5,5

크기가 9인 패턴일때, 비어야 할 곳은 (3,3),(3,4)(3,5),(4,3)(4,4)(4,5)(5,3)(5,4)(5,5)이다.

즉 비어야 할 곳의 구간을 구하는 식을 세우면 ( (size(크기)/3) , (size(크기)/3) )을 시작점으로 행으로 size/3, 열로 size/3의 크기 만큼을 비우게 하면 된다.

 

이를 코드로 표현할 경우

for(int i=size/3;i<(size/3)*2;i++){
            for(int j=size/3;j<(size/3)*2;j++){
                arr[row+i][cols+j]=false; //row와 cols는 시작점을 의미
            }
        }

여기서 주의해야 할 점은 크기와 위치마다 시작하는 점이 다르기에 이를 유의해야 한다. 크기가 9인 패턴의 빈 곳의 시작점은 (3,3)이지만 크기가 3인 패턴의 시작점은 (0,0),(0.3),(0.6)(3,0)...처럼 규칙성을 가지고 변화하기 때문이다. 

 

여기서 규칙이 또 나왔다. 각 패턴의 시작점은 size/3을 기준으로 변한다는것이다.

for(int i=row;i<size+row;i=i+(size/3)){
                for(int j=cols;j<size+cols;j=j+(size/3)){
                    if(size>3)	//크기가 3인 패턴의 빈 공간부터 구하기
                         cus(i,j,size/3);
                    if(count==0) { //크기에 대해 한번씩만 실행해야 되므로 count를 이용
                        input_false(i, j, size);
                        count=1;
                    }
                }
            }

여기서 count를 사용하는 이유는 패턴을 9개로 나눈 후 그것을 반복문을 이용해 돌아가는데 count를 사용 하지 않을경우, 같은것이 여러번 돌아가 제대로 실행 되지 않기때문이다.

 

풀이방식을 그림으로 표현하면

이런식으로 규칙에따라 n=3으로 잘게 쪼갠뒤 빈곳이어야 할 곳에 false를 넣어서 푸는 방식이다.

import java.util.Scanner;

public class Main {

    static boolean[][] arr;

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int size=scanner.nextInt();

        arr=new boolean[size][size];

        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                arr[i][j]=true;
            }
        }
        Main bae=new Main();
        bae.cus(0,0,size);

        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                if(arr[i][j])
                    System.out.print("*");
                else
                    System.out.print(" ");
            }
            System.out.println();
        }

    }

    void input_false(int row, int cols,int size){
        for(int i=size/3;i<(size/3)*2;i++){
            for(int j=size/3;j<(size/3)*2;j++){
                arr[row+i][cols+j]=false;
            }
        }
    }

    void cus(int row,int cols, int size){
        int count=0;
            for(int i=row;i<size+row;i=i+(size/3)){
                for(int j=cols;j<size+cols;j=j+(size/3)){
                    if(size>3)
                         cus(i,j,size/3);
                    if(count==0) {
                        input_false(i, j, size);
                        count=1;
                    }
                }
            }
    }
}