2447번

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

2447번: 별 찍기 - 10

문제는 읽어보면 좋겠다. 나는 처음에 문제 내용도 이해 못했다.. 문해력 키워야지...

주변에 알고리즘 장인들이 많아서 많이 물어보면서 풀었다. 나도 잘하고싶어~~~ㅠㅠ

 

어쨌든 사담은 그만하고 문제에 대해서 설명하겠다.

문제를 간단하게 생각하면 주어진 size에 대해 9등분하여 5번칸을 제외하고 또 각각의 칸을 9등분하는 과정을 반복하는 것이다.

*	*	*	*	*	*	*	*	*
*	X	*	*	X	*	*	X	*
*	*	*	*	*	*	*	*	*
*	*	*	X	X	X	*	X	*
*	X	*	X	X	X	*	X	*
*	*	*	X	X	X	*	*	*
*	*	*	*	*	*	*	*	*
*	X	*	*	X	*	*	X	*
*	*	*	*	*	*	*	*	*

위의 테이블을 보면 9X9짜리 테이블이다. 이 테이블에서 처음 9X9짜리 테이블을 9등분하면 3X3테이블이 9개가 된다는건 다들 알 것이다.

그 9개 중에 5번 테이블을 빼고 나머지를 채우는 것이다.

	1			2			3
			5	5	5
	4		5	5	5		6
			5	5	5
	7			8			9

위에 숫자로 순서를 표시해 보았다. 이렇게 5번째 칸만을 제외하고 나머지 부분을 또 9등분 해서 그 테이블의 5번째 칸만을 제외하고 크기가 나눠야할 칸의 크기가 1이될 때 별을 채우는 것이다.

 

1	1	1
1		1
1	1	1

1번째 칸을 떼와서 한번 더 9등분 해보았다.

이렇게 되면 이제는 9등분한 한칸의 크기가 1이기 때문에 또 9등분할 수 없다.

그렇기 때문에 이제는 그 칸에 *을 찍는 것이다.

*	*	*
*		*
*	*	*

이제 어떤 문제인지는 이해했을 것이라고 믿는다. 하지만 문제는 이해했는데, 이걸 코드로 어떻게 짜야하지?하고 막막한 사람들이 있을 것이다.(나처럼...)

 

이 문제를 단계별 풀어보기에서 보면 '재귀'파트에 들어있다. 그렇다 재귀를 사용할 것이다.

일단 아래의 해답 코드를 읽어보고 아래 설명을 하겠다.(알고리즘 장인분들은 눈감으세요 더러운코드 보는거아니니까)

package backjoon;

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

public class b2447 {
    static char[][] matrix;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());
        matrix = new char[count][count];
        StringBuilder sb = new StringBuilder();
         for(int i=0; i<count; i++){
            for (int j=0; j<count; j++){
                matrix[i][j]=' ';
            }
        }//테이블을 공백으로 다 만든다.

         printStar(count,0,0);//재귀문으로 반복해서 9개 테이블을 만들고, 5번 인덱스만 제외하고 다 재귀를 반복한다.

         for (int i=0; i<count; i++){
             for (int j=0; j<count; j++){
                 sb.append(matrix[i][j]);
             }
             sb.append("\n");
         }
        System.out.println(sb);
    }
    public static void printStar(int size, int x, int y){
        if(size==1){
            matrix[x][y]='*';
            return;
        }
        int count = 0;
        for(int i=x; i<x+size; i+=size/3){//x부터 x+size 까지 3등분한걸 생각한다. 0부터 size 를 3등분해서 x는 0,1,2중 하나
            for(int j=y; j<y+size; j+=size/3){//y부터 y+size 까지 3등분, 0부터 size 를 3등분해서 y는 0,1,2 중 하나
                count++;//9개짜리 테이블 중에 5번일 때는 다음 테이블로 넘어가야 하니까 if문 안에 넣으면 5일때는 안들어가서 안된다.
                if(count!=5){
                    printStar(size/3,i,j);
                }
            }
        }//전체 크기를 3등분씩 해서 9개짜리 테이블로 만든다. 5가 아니면 채운다.
    }
}

 

일단 나는 전역변수로 char배열을 선언했다. 변수명은 matrix라고 설정했다.

이제 이 matrix를 테이블이라고 불르겠다. 이 테이블을 위에 설명했던 것처럼 9등분하는 과정을 반복할 것이다.

그 전에 먼저 *이 아닌 부분은 공백으로 만들기 위해서 별찍기 과정전에 테이블을 모두 공백으로 채운다.

그 다음 별을 찍는 재귀적 메서드를 부를 것이다. 여기서는 이제 x,y좌표를 도입할 것이다.

왜냐하면 테이블을 9등분 하기위해서다. 테이블의 크기를 입력받고 x,y좌표를 입력받아서 테이블을 x축 방향으로 3등분 y축 방향으로 3등분하는 것을 반복문에서 step크기 조절로 할 것이다. 

for(int i=x; i<x+size; i+=size/3){//x부터 x+size 까지 3등분한걸 생각한다. 0부터 size 를 3등분해서 x는 0,1,2중 하나
            for(int j=y; j<y+size; j+=size/3){//y부터 y+size 까지 3등분, 0부터 size 를 3등분해서 y는 0,1,2 중 하나
                count++;//9개짜리 테이블 중에 5번일 때는 다음 테이블로 넘어가야 하니까 if문 안에 넣으면 5일때는 안들어가서 안된다.
                if(count!=5){
                    printStar(size/3,i,j);
                }
            }

이 부분이 위에 설명한 부분이다. 맨처음 size=9이고, x와 y가 0으로 들어오면, x=0일때, y는 3, 6이다.

x가 3이면 똑같이 y는 0,3,6이다. x6의 경우도 같다.

여기서 중요한 것은 x3,y3인 부분은 5번째 칸이기 때문에 다음 9등분 과정을 하지 않는다.

이를 구별하기 위해서 count라는 테이블 번호를 계산하는 변수를 사용한다.

x0,y0			x0,y3			x0,y6
x3,y0						x3,y6
x6,y0			x6,y3			x6,y6

 

그 다음으로 9등분을 시도하면

printStar()문에 x0,y0과 size/3인 3이 들어가면 3/3=1이기 때문에 1칸씩 나눠진다. 그럼 그다음 9등분을 하려고하면 크기가 1이 된다. 그렇기 때문에 아래 테이블에 표시해둔 부분 중에 가운데인 x1,y1을 제외하고는 모두 '*'을 찍는다.

x0,y0	x1,y1	x2,y2
x1,y0		x1,y2
x2,y0	x2,y1	x2,y2

 

테이블을 정리해보면 아래 테이블과 같아질 것이다.

x0,y0	x0,y1	x0,y2	x0,y3	x0,y4	x0,y5	x0,y6	x0,y7	x0,y8
x1,y0	x1,y1	x1,y2	x1,y3	x1,y4	x1,y5	x1,y6	x1,y7	x1,y8
x2,y0	x2,y1	x2,y2	x2,y3	x2,y4	x2,y5	x2,y6	x2,y7	x2,y8
x3,y0	x3,y1	x3,y2	x3,y3	x3,y4	x3,y5	x3,y6	x3,y7	x3,y8
x4,y0	x4,y1	x4,y2	x4,y3	x4,y4	x4,y5	x4,y6	x4,y7	x4,y8
x5,y0	x5,y1	x5,y2	x5,y3	x5,y4	x5,y5	x5,y6	x5,y7	x5,y8
x6,y0	x6,y1	x6,y2	x6,y3	x6,y4	x6,y5	x6,y6	x6,y7	x6,y8
x7,y0	x7,y1	x7,y2	x7,y3	x7,y4	x7,y5	x7,y6	x7,y7	x7,y8
x8,y0	x8,y1	x8,y2	x8,y3	x8,y4	x8,y5	x8,y6	x8,y7	x8,y8

그럼 이제 테이블에 별을 찍는 것까지 완료했다.

만약 시간초과가 나는 사람이 있다면 아마 System Input/Output(I/O)과정을 여러번하여서 그럴 것이다.

이걸 막기위해서는 StringBuilder를 사용하여 한번에 출력하는 방식을 사용하면 된다.

그 부분은 위의 정답코드에 나와있으니 읽어보면서 이해하면 좋을 것 같다.