[알고리즘] BOJ 2447 별 찍기-10 (JAVA)

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

2447번: 별 찍기 - 10

문제만 봐서는 난이도는 골드5에 아웃풋에 찍힌 수많은 별을 보며 겁먹기 쉬운데,

사실 앞서 풀었던 Z문제(BOJ 1074,실버1)이나 색종이 만들기(BOJ 2630, 실버2)와 비슷한 방식으로 접근하면 되고

방법만 캐치하면 금방 풀 수 있는 문제였다.

우선 문제에 예시로 주어진 그림 N=27에서의 출력값을 보면, 하나의 큰 패턴이 3 X 3 의 형태에 가운데만 비어있는

형식이고 각각의 패턴에는 똑같이 하나의 패턴이 3 X 3 형태로 되어있다.

반복문을 막 배울 때 하던 별찍기 문제들처럼 for문 안에 동작 조건을 조작해서 print("*") 을 매번 수행하는 형태는 힘들고,

char 2차원 배열을 선언하여 별을 채워주는 식으로 진행하는 편이 수월하다.

import java.io.*;

import java.util.*;

public class boj2447 {

    static int N;

    static char square[][];

    public static void IHateStar(int srcI, int srcJ, int destI, int destJ) {

        int idx, i, j;

        if (srcI + 3 != destI && srcJ + 3 != destJ) {

            idx = 0;

            for (i = srcI; i < destI; i += ((destI - srcI) / 3)) {

                for (j = srcJ; j < destJ; j += ((destJ - srcJ) / 3)) {

                    idx++;

                    if (idx == 5) {

                        continue;

                    }

                    IHateStar(i, j, i + ((destI - srcI) / 3), j + ((destJ - srcJ) / 3));

                }

            }

        } else {

            idx = 0;

            for (i = srcI; i < srcI + 3; i++) {

                for (j = srcJ; j < srcJ + 3; j++) {

                    idx++;

                    if (idx == 5) {

                        continue;

                    }

                    square[i][j] = '*';

                }

            }

        }

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        square = new char[N][N];

        for (int i = 0; i < N; i++) {

            for (int j = 0; j < N; j++) {

                square[i][j] = ' ';

            }

        }

        IHateStar(0, 0, N, N);

        for (int i = 0; i < N; i++) {

            sb.append(square[i]).append('\n');

        }

        System.out.println(sb);

    }

}

 

가장 작은 패턴에 도달하기까지, 9개로 분할된 지역에 재귀 형태로 값을 넣어 실행시키는데,

가운데는 비어있으므로 그 부분에서는 해당 재귀를 호출하지 않도록 구현했다.

가장 작은 패턴에 도달하면(src + 3 == dest 이면), 해당 패턴에서도 가운데는 마찬가지로 비어있으므로 가운데를 제외한 나머지 구역에 별* 을 찍어준다.

아래에 시간 초과가 걸렸던 이유는, 출력시 그냥 아무 생각없이 2중 반복문으로 출력해줬더니 시간초과가 났다.

StringBuilder를 활용하는 것이 매 줄마다 System.out.println을 쓰는 것보다 시간 절약이 많이 되기 때문에 변경했더니 바로 통과가 되었다.