[백준] 2448. 별 찍기 11

문제 링크

[백준] 2448. 별 찍기 11

풀이 과정

[백준] 2447. 별 찍기 10 과 같은 방법으로 생각했습니다.

N은 $3*2^k$이므로, 3, 6, 12, 24, … 등으로 주어집니다. 문제 예제에서는 N이 24인 패턴이 주어졌으므로, N이 3일 때, 6일 때를 직접 그려가며 규칙을 찾았습니다.

먼저 N이 3일 때를 그려봤습니다. 패턴의 정 가운데는 (1, 2)이고, 이를 기준으로 8방향에 대해 별을 그릴 수 있음을 알 수 있습니다.

N이 6일 때의 패턴 모양은 위와 같습니다. 패턴의 정 가운데는 (3, 5)이며, 이를 기준으로 세 곳에 대해 N이 3일 때의 패턴을 그리는 것을 알 수 있습니다.

N이 12일 때의 패턴 모양은 위와 같습니다. 패턴의 정 가운데는 (6, 11)이며, 이를 기준으로 세 곳에 대해 N이 6일 때의 패턴을 그리는 것을 알 수 있습니다.

따라서, 다음과 같은 규칙을 일반화할 수 있습니다.

• N이 3일때는 8방향에 대해 별을 그린다.
• N이 6 이상일 때는, 3방향에 대해 N/2 일때의 패턴을 그린다.

static void solve(int n, int x, int y) {
    if (n == 3) {
        for (int d = 0; d < 8; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            map[nx][ny] = '*';
        }

        return;
    } else if (n == 6) {
        for (int d = 0; d < 3; d++) {
            int nx = x + ddx[d], ny = y + ddy[d];
            solve(n / 2, nx, ny);
        }
    } else {
        solve(n / 2, x - n / 4, y);
        solve(n / 2, x + n / 4, y - n / 2);
        solve(n / 2, x + n / 4, y + n / 2);
    }
}

따라서, 위와 같이 N의 값에 따라 별을 그릴 수 있습니다.

• N이 3일 때는, 8방향에 대해 별을 그린다.
• N이 6일 때는, 위의 빨간 화살표 만큼의 델타 배열을 이동시킨 좌표를 중앙으로 하여, N을 3으로 재귀 함수를 호출한다.
• N이 12 이상일 때는, 세 방향 각각에 대해 N/2 사이즈와 정 가운데 좌표를 전달하는 재귀 함수를 호출한다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static char[][] map;
    static int[] dx = {-1, 0, 0, 1, 1, 1, 1, 1}, dy = {0, -1, 1, -2, -1, 0, 1, 2};
    static int[] ddx = {-2, 1, 1}, ddy = {0, -3, 3};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        map = new char[N][N * 2 - 1];

        for (int i = 0; i < N; i++) Arrays.fill(map[i], ' ');

        solve(N, N / 2, N - 1);

        StringBuilder answer = new StringBuilder();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N * 2 - 1; j++) {
                answer.append(map[i][j]);
            }
            answer.append("\n");
        }

        System.out.println(answer);
    }

    static void solve(int n, int x, int y) {
        if (n == 3) {
            for (int d = 0; d < 8; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                map[nx][ny] = '*';
            }

            return;
        } else if (n == 6) {
            for (int d = 0; d < 3; d++) {
                int nx = x + ddx[d], ny = y + ddy[d];
                solve(n / 2, nx, ny);
            }
        } else {
            solve(n / 2, x - n / 4, y);
            solve(n / 2, x + n / 4, y - n / 2);
            solve(n / 2, x + n / 4, y + n / 2);
        }
    }
}