BOJ_2448 : 별 찍기 - 11

👉 문제링크

2448번: 별 찍기 - 11

---

---

🔸 문제 분석 🔸

• N이 3x2^k (0<= k <=10)로 입력된다.
  • 출력 형식처럼 재귀 형식의 피라미드 별찍기를 구현한다.

🔸 문제 풀이 🔸

• 누가봐도 재귀적인 특징이 보이는데, 규칙을 정의해보자.

  *  
 * * 
*****

• 먼저 N이 가장 작게 입력됐을 경우는 3일 때이다.
• 더 작은 단계로 갈 수 없으므로, 줄 번호가 1, 2, 3 일 때로 나누어서 *, * *, ***** 를 출력하도록 했다.

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

• 다음은 N이 6일때 이다. 앞선 N이 3인 경우의 모양이 3번들어간다.
• 여기서 규칙을 볼 수 있는데, 중간 아래쪽으로는 N이 3인 피라미드가 2개, 뒤집힌 공백 삼각형이 그 사이에 들어간 모양이다.

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

• N이 12인 경우는 N이 6인 경우가 마찬가지로 2번나오고 가운데 뒤집힌 공백 삼각형이 들어간 모습이다.
  • 포스팅 하단의 그림을 보면 이해하기 편할 것이다.
• 따라서 각 줄마다 직전 삼각형의 높이를 알아야하는데, 어느 3*2^k ~ 3*2^k' 범위에 속한지 찾고, 3*2^k를 구하면 된다.
• 직전 삼각형의 높이(3*2^k)를 찾았으면, 현재 줄 번호에서 직전 높이를 빼서 재귀를 위한 줄 번호를 구할 수 있다.
  • 이렇게 구한 줄 번호가 안에 들어가 있는 삼각형의 줄 번호이다.

🔸 코드 🔸

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

public class Main {
    private static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < N - i; j++) {
                sb.append(' ');
            }
            recursion(i);
            for (int j = 0; j < N - i; j++) {
                sb.append(' ');
            }
            sb.append('\n');
        }
        sb.deleteCharAt(sb.length() - 1);
        bw.write(sb.toString());
        bw.flush();
    }

    private static void recursion(int n) {
        if (n == 1) {
            sb.append('*');
        } else if (n == 2) {
            sb.append('*');
            sb.append(' ');
            sb.append('*');
        } else if (n == 3) {
            for (int i = 0; i < 5; i++) {
                sb.append('*');
            }
        } else {    // 재귀
            int before_max = find_before_max(n);
            recursion(n - before_max);
            for (int i = 0; i < (before_max * 2 - n + 1) * 2 - 1; i++) {
                sb.append(' ');
            }
            recursion(n - before_max);
        }
    }

    private static int find_before_max(int n) {
        if (n <= 3) {
            return 0;
        }

        int i = 0;
        double num = 3 * Math.pow(2, i);

        while (num < n) {
            num = 3 * Math.pow(2, ++i);
        }

        return (int) (3 * Math.pow(2, i - 1));
    }
}

🔸 코드 해석 🔸

• main 메서드에서 피라미드 앞 뒤 공백을 채운다.
• 재귀 메서드 recursion에서 피라미드 안쪽의 별과 공백을 채운다.
• find_before_max 메서드에서 직전 삼각형의 높이를 구한다.
• 재귀 메서드는 다음과 같이 진행된다.
  • 줄번호 n이 1, 2, 3인 경우는 정해진 모양을 출력한다.
  • 그 외에는 직전 삼각형, 공백 삼각형, 직전 삼각형을 출력해야한다.
  • 직전 삼각형을 출력할 때 재귀를 이용한다.

---

🔸 end 🔸

• 오랜만에 재귀 문제에 잘못걸려서 아주아주 고생했다.
  • 계속 풀리지 않았지만, 오기로 풀이를 보지않고 진행해서 3일이나 걸렸다.
  • 코테 스트릭이 끊겼다가 다시 시작하는 마음가짐으로 풀이를 최대한 보지 않았다.
• 아쉬운 점은 조금 번거로워서 문제를 손으로 풀이해가며 접근하지 않다가, 결국 오늘 손으로 적어가며 풀었더니 풀렸다.
  • 진작에 꼼꼼하게 풀이할 껄 후회된다.
  • 다음은 풀이하면서 그린 위에서 언급한 참고 그림이다.