[백준] no2448: 별 찍기11 - 재귀

문제

N = 3 * 2^k 이며, 이유는 최소  삼각형이 총 세줄로 되어있기 때문이다.

(단, 0<= k <=10)

N이 주어질 때,  N높이 * (N*2 -1)너비의 캔버스 안에 별을 조건에 맞게 찍어 출력해라

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

---

원리

재귀를 이용해, 아래의 최소 삼각형이 된 순간에 별을 찍게끔 한다.

즉, 더이상 쪼갤 수 없는 삼각형이 될 때까지 쪼개서, 최소 삼각형 단위로 별을 찍어서 N사이즈의 삼각형을 만들어 냄

  *       // 셋째 칸
 * *      // 2,4째 칸
*****     // 1~5째 칸

 

---

나의 코드

import java.io.*;
import java.util.Arrays;

public class no2448 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static char[][] tree;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());  // N = 3 * 2^k
        tree = new char[N][N*2-1]; // 캔버스 사이즈는 N
        for(int i=0 ; i<N ; i++) Arrays.fill(tree[i], ' '); // 우선 캔버스를 다 공백으로 채움(별 사이는 전부 공백이므로)

        // 실질적인 별찍기를 위한 재귀 메소드
        make_tree(0, N-1, N);  // 세로 좌표는 0부터, 가로 좌표는 N-1인 중간부터 찍기 시작함


        // 결과가 입력된 배열을 순회하며 출력에 담음
        for(int i=0 ; i< N ; i++) {
            for(int j=0 ; j< N*2-1 ; j++) {
                bw.append(tree[i][j]);
            }
            bw.write("\n");
        }

        bw.close();
    }

    private static void make_tree (int y, int x, int N) {
        // 최소 삼각형까지 쪼갰을 때, 삼각형으로 별 찍어줌
        if(N==3) {
            tree[y][x] = '*'; // 최소 삼각형의 첫 번째 줄
            tree[y+1][x-1] = tree[y+1][x+1] = '*'; // 최소 삼각형의 두 번째 줄
            tree[y+2][x-2] = tree[y+2][x-1] = tree[y+2][x] = tree[y+2][x+1] = tree[y+2][x+2] ='*'; // 최소 삼각형의 세 번째 줄
        }
        // 쪼갤 수 있는 삼각형인 경우, 쪼갬
        else {
            int cut = N/2;  // 만약 3개의 삼각형으로 쪼갤 수 있는 큰 삼각형인 경우, 쪼개버림
            make_tree(y,x,cut);  // 위쪽 삼각형
            make_tree(y+cut, x-cut , cut);  // 왼쪽 삼각형
            make_tree(y+cut, x+cut , cut);  // 오른쪽 삼각형
        }
    }
}

 

---

레퍼런스

참고링크 : https://velog.io/@jii0_0/%EB%B0%B1%EC%A4%80-2448.-%EB%B3%84-%EC%B0%8D%EA%B8%B0-11-Java