백준 별 찍기 - 10 (2447번) 자바 풀이

문제 설명

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

 

입력 예제

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

 

- 예제 입력 1

27​

 

- 예제 출력 1

문제 접근 방식

1. 시간 복잡도

우선 알고리즘 구현 시 시간복잡도를 확인해봤을 떄, N은 3의 거듭제곱, 1<=N<=6561(3^8) N의 최대값을 확인해봤을때 시간복잡도는 최대 O(N^2)까지 구현가능합니다. 시간복잡도는 큰 제한이 없는 것을 확인했으니 접근 방법에 대해 생각해볼 필요가 있습니다.

 

2. 접근방식

 

이 문제는 규칙을 파악해서 어떻게 구현해야되는지 파악하는 것이 이 문제의 관건이였던 것 같습니다. 저도 규칙을 찾아 적용하는데 까지 시간이 꽤 걸렸습니다.

 

우선 주어진 문제 예제에서 N=3일때, 별찍는 모양은 아래와 같습니다.

이 모양을 보고 유추했을때, 가운데를 제외한 나머지 부분 테두리는 별을 찍는 것을 유추할 수 있었습니다.

 

그러면 N=3^2=9 일때는 어떻게 찍을 것인지 예상되는 그림은 아래와 같습니다.

9일때 역시 가운데 부분은 별을 찍지 않고 테두리만 별을 찍는 것으로 확인합니다.

 

N=3^3=27

전체적인 그림을 봤을때 N이 27일때 9로 별찍기 한 갯수 9개, N이 9개일때 3으로 별찍기 한 갯수 9개가 있는 것을 확인할 수 있습니다.

여기서 또 한가지 규칙이 존재하는데 가운데 값에는 별을 찍지 않는 것 입니다. 이번엔 거꾸로 3부터 확인해보겠습니다.

N이 3일때 왼쪽 -> 오른쪽 순서대로 보면 5번째는 별을 찍지 않습니다. N이 9일때도 5번째 칸에는 별을 찍지 않습니다. 마지막 N이 27일 때 역시 5번째 칸에는 별을 찍지 않습니다.

 

이렇게 알게된 규칙 2가지는

1. 3부터 -> 3^k값은 별찍기 오름차순의 갯수

2. 5번째는 별을 찍지 않는다.

 

문제풀이

class Main2447{

	    static void start ( int x, int y, int n, boolean blank ) {
			
            // 공백일때
            if ( blank ) {
                for ( int i = x; i < x + n; i++ ) {
                    for ( int j = y; j < y + n; j++ ) {
                        arr[i][j] = ' ';
                    }
                }
                return;
            }
			// 더 이상 쪼갤수 없는 블록
            if ( n == 1 ) {
                arr[x][y] = '*';
                return;
            }

            int size = n / 3;
            int count = 0; // count는 별 누적을 의미
            for ( int i = x; i < x + n; i += size ) {
                for ( int j = y; j < y + n; j += size ) {
                    count++;
                    // count가 5번째 일 경우, 공백으로 계산
                    start( i, j, size, count == 5 );
                }
            }

    }
}

 

전체 소스코드는 아래링크에 있습니다. 

 

https://github.com/algorithm-cote-study/baekjoon-algorithm/blob/yeji/src/main/java/org/backjoon/class3/yeji/Main2447.java

GitHub - algorithm-cote-study/baekjoon-algorithm: 알고리즘까지 브론즈가 될 수 없어