[백준] 2448번 : 별 찍기 - 11 Gold4(골드4) - JAVA[자바]

[Gold IV] 별 찍기 - 11 - 2448

문제 링크

성능 요약

메모리: 234796 KB, 시간: 476 ms

분류

재귀

제출 일자

2024년 1월 19일 00:23:23

문제 설명

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

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

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

접근 방법

1. 주어진 예시를 본다면 N이 3일 때 3층짜리 삼각형이고 맨 아랫줄은 6개의 공간이 생기는 것을 알 수 있다.

2. 출발점에서 시작하여 밑변의 길이를 2로 나누면 아래층의 시작점을 나눌 수 있다.

3. 밑변의 길이를 2로 나눈 것을 한번 더 나눠준다면(높이는 N이고 너비는 2 * N이기때문에) 가운데 시작점을 찾을 수 있다.

4. 길이가 총 6이 된다면(N = 3이 최소값이고 너비가 N * 2인 6이 너비의 최소값) 시작점을 기준으로 별을 넣어주면 된다.

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

public class Main {
    // 별을 저장하기 위한 배열
    static char[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        // n은 3의 배수
        int n = Integer.parseInt(br.readLine());
        // n이라면 3층짜리 배열에 맨 아랫줄은 별이 6개
        map = new char[n][n * 2];
        // 공백으로 초기화 시켜준다.
        for (int i = 0; i < map.length; i++) {
            Arrays.fill(map[i], ' ');
        }

        // 별을 채우는 재귀 호출
        star(n - 1, 0, n * 2);

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                sb.append(map[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    private static void star(int x, int y, int len) {
        // len이 6이라면 3층짜리 삼각형 한개라서 채워주고 종료
        if (len == 6) {
            // 1층
            map[x][y] = map[x][y+1] = map[x][y+2] = map[x][y+3] = map[x][y+4] = '*';
            // 2층
            map[x - 1][y + 1] = map[x - 1][y + 3] = '*';
            // 3층
            map[x - 2][y + 2] = '*';
            // 종료
            return;
        }
        // 다음 길이는 현재 변의 길이의 나누기 2
        int nextLen = len / 2;
        // 왼쪽 아래 삼각형
        star(x, y, nextLen);
        // 오른쪽 아래 삼각형
        star(x, y + nextLen, nextLen);
        // 가운데 삼각형 높이고 len은 2 *n이 기준이기 때문에 나누기 2를 해주면 구할 수 있다.
        star(x - nextLen / 2, y + nextLen / 2, nextLen);
    }
}