[백준 JAVA] 2448번: 별 찍기 - 11

https://www.acmicpc.net/problem/2448

 

문제를 처음 보면 단순 구현처럼 보이지만 실제로는 재귀 구조를 이해해야 풀리는 문제였다.
나도 처음에는 감이 잘 안 잡혀서 막히는 느낌이 있었는데 핵심은 삼각형을 어떻게 쪼개느냐였다.

 

이 문제는 높이 N의 큰 삼각형이 있다고 할 때, 이걸 한 번에 그리는 게 아니라 작은 삼각형 3개로 분할해서 생각해야 한다.

높이 N짜리 삼각형은 다음과 같이 구성된다.

• 위에 높이 N/2짜리 삼각형 1개
• 아래에 높이 N/2짜리 삼각형 2개 (왼쪽, 오른쪽)

즉 하나의 삼각형을 계속 절반으로 쪼개면서 그리는 구조다.
이걸 재귀로 표현하면 자연스럽게 해결된다.

 

좌표를 어떻게 잡느냐도 중요하다.

이 문제에서는 (x, y)를 삼각형의 꼭대기 좌표라고 정의한다.

처음 시작은 전체 삼각형의 꼭대기이므로

• 행: 0 (맨 위)
• 열: N - 1 (가운데)

즉 시작 호출은

draw(0, N - 1, N)

 

이렇게 된다.

 

배열 크기도 헷갈리기 쉬운 부분인데,
삼각형의 밑변을 기준으로 생각하면 이해가 쉽다.

높이가 N일 때 아래로 한 줄 내려갈 때마다 좌우로 1칸씩 퍼지기 때문에
맨 아래 줄은

• 왼쪽으로 N - 1칸
• 오른쪽으로 N - 1칸

퍼진다.

그래서 전체 너비는

2 * N - 1

 

이 된다.

 

재귀 함수의 핵심은 다음과 같다.

draw(x, y, size)

 

• (x, y) : 삼각형의 꼭대기 좌표
• size : 삼각형의 높이

1. 종료 조건

높이가 3일 때는 더 쪼갤 수 없으므로 직접 별을 찍는다.

*
* *
*****

 

이걸 좌표 기준으로 찍어주면 된다.

2. 재귀 분할

높이가 3보다 크면, 삼각형을 3개로 나눈다.

• 위 삼각형: (x, y)
• 왼쪽 아래: (x + size/2, y - size/2)
• 오른쪽 아래: (x + size/2, y + size/2)

이렇게 각각 다시 draw를 호출한다.

 

전체 코드는 다음과 같다.

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

public class Main {
    static int N;
    static StringBuilder sb = new StringBuilder();
    static char[][] stars;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        stars = new char[N][2 * N - 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 2 * N - 1; j++) {
                stars[i][j] = ' ';
            }
        }

        draw(0, N - 1, N);

        for (int i = 0; i < N; i++) {
            sb.append(stars[i]).append('\n');
        }

        System.out.println(sb);
    }

    private static void draw(int r, int c, int size) {
        if (size == 3) {
            stars[r][c] = '*';
            stars[r + 1][c - 1] = '*';
            stars[r + 1][c + 1] = '*';
            for (int i = -2; i <= 2; i++) {
                stars[r + 2][c + i] = '*';
            }
            return;
        }

        int half = size / 2;

        draw(r, c, half);
        draw(r + half, c - half, half);
        draw(r + half, c + half, half);
    }
}

---

이 문제를 풀면서 느낀 건, 단순히 별을 찍는 문제가 아니라
큰 문제를 작은 문제로 나누는 방식을 연습하는 문제라는 점이었다.

처음에는 좌표가 헷갈리고 왜 이렇게 나누는지 감이 안 오는데
삼각형을 직접 그려보면서

• 꼭대기 기준으로 생각하기
• 좌우로 퍼지는 구조 이해하기

이 두 가지만 잡히면 훨씬 쉽게 접근할 수 있다.

비슷한 유형의 재귀 문제를 풀 때도 같은 방식으로 접근하면 도움이 된다.