백준 2448번: 별 찍기 - 11

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

문제 풀이

재귀

arr = N x (2N - 1) 크기의 삼각형이 이루어지려면 어디에 별을 찍어야 하는지

solve(N, y, x) = 현재 N x (2N - 1) 크기의 삼각형의 맨 윗점 (y, x)에 대해 N / 2 x (2N - 1) / 2 크기의 삼각형들의 맨 윗점을 구하는 재귀 함수

star(y, x) = (y, x) 점을 맨 윗 점으로 하는 3 x 5 크기의 삼각형을 그리는 함수

solve 함수를 통해 3 x 5 크기의 삼각형을 그려야 하는 맨 윗점들을 모두 구해 그 점에 대해 star 함수를 실행해 arr 배열에 별이 찍혀야 하는 위치에 별을 저장한다.

그 이후에 arr 배열을 출력하면 정답.

풀이 설명

첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)

N x (2N - 1) 크기의 가운데가 빈 삼각형을 그리는 문제다. 예를 들어 N이 24일 때 출력되는 삼각형은 다음과 같다.

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

이 예제를 보면 N x (2N - 1) 크기의 삼각형은 가운데가 비어있고 N / 2 x (2N - 1) / 2 크기의 삼각형 3개로 이루어진다는 것을 알 수 있다.

여기서 맨 왼쪽 위 칸의 좌표를 (1, 1)로 두었을 때 삼각형 맨 위의 좌표는 (1, 24)라는 것을 알 수 있고, 3등분 한 삼각형의 맨 윗 점의 좌표는 (1, 24), (13, 12), (13, 36)이라는 것을 알 수 있다.

이 세 점에서 패턴을 발견할 수 있는데 가장 먼저 구했던 현재 삼각형의 맨 위의 좌표와 거기서 y 좌표에는 N / 2만큼 더했고 x 좌표에서는 N / 2만큼 더하고 뺀 좌표가 나와있다는 것을 알 수 있다.

결론적으로 이 문제는 3 x 5 크기의 삼각형을 패턴에 따라 그리는 문제이므로 방금 구한것처럼 삼각형의 맨 윗점을 계속 N을 절반만큼 나눠서 구하다 보면 현재 그려야 하는 3 x 5 크기의 삼각형의 맨 윗점을 모두 구할 수 있다.

그러므로 삼각형의 맨 윗점을 구하는 재귀함수 solve를 만들어 인수로 들어오는 N이 3이 되기 전까지 계속 절반으로 나누어 삼등분되는 삼각형의 맨 윗점들을 계속 구하고 N이 3이 될 때 그 구했던 삼각형의 맨 윗점들에 대해 그 점에서의 3 x 5 크기의 삼각형을 그리는 함수 star에 인수로 점을 넘겨서 3 x 5 크기의 삼각형을 별로 나타내 그리면 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val N = nextInt()
    val arr = Array(N){ CharArray(2 * N - 1){' '} }
    fun star(y: Int, x: Int){
        if(y >= N) return
        arr[y][x] = '*'
        arr[y + 1][x - 1] = '*'
        arr[y + 1][x + 1] = '*'
        for(i in 0..2){
            arr[y + 2][x - i] = '*'
            arr[y + 2][x + i] = '*'
        }
    }
    fun solve(N: Int, y: Int, x: Int){
        if(N == 3){
            star(y, x)
        } else {
            solve(N / 2, y, x)
            solve(N / 2, y + N / 2, x + N / 2)
            solve(N / 2, y + N / 2, x - N / 2)
        }
    }
    solve(N, 0, N - 1)
    val bw = System.out.bufferedWriter()
    for(charArray in arr){
        bw.write(charArray)
        bw.newLine()
    }
    bw.flush()
    bw.close()
}