방과후
ALGORITHM NOTE약 1분

BOJ 2448 - 별 찍기 - 11

삼각삼각 별

#algorithm#boj#gold#recursion
아카이브로 돌아가기

문제 링크

문제

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

입력

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

출력

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

풀이

전체 도형을 한 번에 그리는 것이 아니라, 더 작은 기본 패턴을 재귀적으로 배치한다고 생각하면 된다. 문제에서 요구하는 별 모양이 자기 유사 구조를 갖기 때문에 분할 정복이 자연스럽다.

코드에서는 현재 크기의 패턴을 여러 개의 하위 패턴으로 나누어 배치하고, 비워야 할 칸이나 채워야 할 칸만 규칙대로 처리한다. 가장 작은 기본 크기에서는 직접 별을 그리며 종료한다.

즉 출력량은 많지만 아이디어 자체는 재귀 패턴 생성이다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    private static char[][] map;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int N = Integer.parseInt(br.readLine());
        map = new char[N][N * 2];
 
        for (int i = 0; i < N; i++) {
            Arrays.fill(map[i], ' ');
        }
 
        solve(0, N - 1, N);
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N * 2; j++) {
                sb.append(map[i][j]);
            }
            sb.append('\n');
        }
 
        System.out.println(sb);
    }
 
    private static void solve(int r, int c, int size) {
        if (size == 3) {
            map[r][c] = '*';
            map[r + 1][c - 1] = map[r + 1][c + 1] = '*';
            map[r + 2][c - 2] = map[r + 2][c - 1] = map[r + 2][c] = map[r + 2][c + 1] = map[r + 2][c + 2] = '*';
            return;
        }
 
        size /= 2;
        solve(r, c, size);
        solve(r + size, c - size, size);
        solve(r + size, c + size, size);
    }
}

복잡도

  • 시간 복잡도: 출력해야 하는 삼각형 영역을 채우므로 O(N2)O(N^2)이다.
  • 공간 복잡도: 그림 저장 배열을 사용하므로 O(N2)O(N^2)이다.

마무리

별 찍기 문제는 결국 패턴을 얼마나 잘 쪼개서 다시 놓느냐의 문제다. 기본 모양과 재귀 배치 규칙만 잡으면 큰 그림도 그대로 따라온다.