[백준] 2448: 별찍기 11 - Java (RecursiveFunction)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 
 
 

  접근 방식

 
출력은 아래와 같다. 먼저 패턴을 살펴보기로 했다. 재귀를 사용해서 문제를 풀어야 하는데, 다음 유의점을 생각하면서 재귀를 구현하였다.
 
1. Base Case 부터 출력한다.
2. 작은 삼각형 출력을 목표로 하고 목표에 맞게 재귀를 호출한다.
3. n / 2 를 하고 위쪽 삼각형, 왼쪽 삼각형, 오른쪽 삼각형을 출력하게 한다.
 
입력으로 24 가 들어올 때 아래와 같이 출력이 되어야 한다.
 

 
 
이 문제에서 가장 핵심적인 부분은 재귀도 있지만 n / 2 부분인데, space 영역을 살펴보면 안쪽 빈 삼각형은 n / 2 를 기준으로 한다는 것을 쉽게 알 수 있을 것이다. 이 부분에서 n / 2 를 하게 되었다. 그리고 3 * (2^k) 으로 입력이 들어온다고 문제에 작성이 되어있으니 이 점을 유의해서 문제를 구현해 보자.
 
 

  풀이

 
설계 내용
 

package src.Homework;

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

public class 별찍기_2448 {
    static char[][] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        arr = new char[n][2 * n - 1];

        // 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2 * n - 1; j++) {
                arr[i][j] = ' ';
            }
        }

        // 메서드 실행
        solution(0, n - 1, n);

        StringBuilder sb = new StringBuilder();

        //
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2 * n - 1; j++) {
                sb.append(arr[i][j]);
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }


    // 별 찍기 재귀 함수
    static void solution(int x, int y, int n) {

        // 탈출부분(Base case)
        if (n == 3) {
            arr[x][y] = '*';
            arr[x + 1][y - 1] = '*';
            arr[x + 1][y + 1] = '*';
            arr[x + 2][y - 2] = '*';
            arr[x + 2][y - 1] = '*';
            arr[x + 2][y] = '*';
            arr[x + 2][y + 1] = '*';
            arr[x + 2][y + 2] = '*';
            return;
        }

        int ns = n / 2;

        // 재귀부분(Recursive Case)
        // 상단 삼각형
        solution(x, y, ns);

        // 왼쪽 하단 삼각형
        solution(x + ns, y - ns, ns);

        // 오른쪽 하단 삼각형
        solution(x + ns, y + ns, ns);
    }
}