본문 바로가기
백준

[백준] 알고리즘 분류(재귀, JAVA)2448번, 별 찍기 - 11

by 열정적인 이찬형 2023. 1. 24.

문제 링크

 

2448번: 별 찍기 - 11

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

www.acmicpc.net


주의사항

  • JAVA를 사용하여 프로그램을 사용하였습니다.
  • 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{ 	
	public static void main(String[] args){
    }
}

문제 설명


접근 방법

이 문제에 핵심

 

1. 예제에 맞게 별을 찍어야합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 재귀를 통해서 별 찍기를 진행합니다.

 

3. 별 찍기를 진행한 결과를 출력합니다.

 

별 찍기!

 

N = 3일 때

k = 0

 

   *                       

  * *                       
 *****

= 별 찍기 기본 모양 출력

 

N = 6

k = 1

 

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

 

아래 쪽을 살펴보면

 

위에 별 찍기 기준

 

4번째 행 : "  *  " + " " +  "  *  "

5번째 행 : " * * " + " " + " * * "

6번째 행 : "*****" + " " + "*****"

 

점화식 : 대응하는 위치 별 + " " + 대응하는 위치 별

대응하는 위치 별 = 아래쪽 열 개수 × " " + 대응하는 위치 별
1번째 행 : 아래쪽 열 개수(3개) × " " + "  *  " = "     *     "

 

N = 12

k = 2

 

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

 

점화식을 그대로 적용시키면

 

12번째 행 : "***** *****" + " " + "***** *****" = ***** ***** ***** *****

 

위와 아래 부분을 구분한 뒤 점화식을 이용하여 별찍기를 진행하면 됩니다.

 

아래 부분 최대 행 : 3 × 2ⁿ

위와 아래를 구분하는 라인 : (3 × 2ⁿ) ÷ 2

 

Why? 위와 아래 부분은 전체 행에 2개 부분으로 구역이 나눠지기 때문입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 24

 

기본 별찍기 모형 설정!

map[0] = "  *  "

map[1] = " * * "

map[2] = "*****"

2. 재귀를 통해서 별 찍기를 진행합니다.

 

N = 24 = 3× 2³

: k가 3이 될 때까지 진행!

 

k = 0

 

  *                        
 * *                       
*****

 

 

k = 1

 

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

 

k = 2

 

 

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

 

k = 3

 

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

 

3. 별 찍기를 진행한 결과를 출력합니다.

 

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

결과로 출력합니다.

 

  • BufferedReader를 사용하여 입력되는 정보를 저장합니다.
  • writeStar 함수를 진행하여 얻은 별 찍기 결과를 BufferedWriter 저장하였습니다.
  • BufferedWriter에 저장된 결과값을 출력하였습니다.
  • writeStar함수는 k값과 점화식을 이용하여 별 찍기를 진행합니다.

 

결과코드

 

import java.io.*;
public class Main {
    static String[] star;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        star = new String[N];
        //별 기본 모양 저장! k = 0
        star[0] = "  *  ";
        star[1] = " * * ";
        star[2] = "*****";
        //별 찍기 진행!
        for(int i=1; 3 * Math.pow(2, i) <= N;i++)
            writeStar(i);
            
        //별 찍기 결과 BufferedWriter 저장
        for(int i=0;i<N;i++)
            bw.write(star[i] + "\n");

        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //k값 점화식을 통한 별 찍기 진행
    static void writeStar(int i) {
        int bottom = (int) (3 * Math.pow(2, i));	//아래 최대 행
        int middle = bottom/2;	//위와 아래를 구분하는 행
        //아래 부분 대응하는 별 점화식 적용
        for(int j=middle;j<bottom;j++)
            star[j] = star[j-middle] + " " + star[j-middle];
        String blank = " ".repeat(middle);
        //위 부분 대응하는 별에 빈 칸 추가!
        for(int j=0;j<middle;j++)
            star[j] = blank + star[j] + blank;
    }
}

댓글