[BOJ] 2448 - 별 찍기 - 11 JAVA

www.acmicpc.net/problem/2448

2448번: 별 찍기 - 11

문제

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

입력

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

출력

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

예제 입력 1

24

예제 출력 1

백준에서 직접 확인

 

 

 

 

 

 

 

풀이 .

import java.io.*;

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringBuilder sb = null;
    static String[] arr = null;
    static int n;

    public static void divideAndConquer(int k) {
        int end = 3 * (int)Math.pow(2, k);  // k가 커질 때마다 라인이 두배씩 늘어난다
        int mid = end / 2;

        for(int i = mid; i < end; i++) {  // 아래쪽 라인 절반은 위쪽 라인 절반을 공백을 사이에 두고 두 번 이어붙인 것이다
            arr[i] = arr[i - mid] + " " + arr[i - mid];
        }

        sb.delete(0, sb.length());
        while(sb.length() < mid) {
            sb.append(" ");
        }

        for(int i = 0; i < mid; i++) {  // 위쪽 절반 라인은 양옆에 전체 라인 수의 절반만큼 공백이 추가된다
            arr[i] = sb.toString() + arr[i] + sb.toString();
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        arr = new String[n];

        arr[0] = "  *  ";
        arr[1] = " * * ";
        arr[2] = "*****";

        for(int k = 1; 3 * (int)Math.pow(2, k) <= n; k++) {
            divideAndConquer(k);
        }

        sb.delete(0, sb.length());
        for(int i = 0; i < n; i++) {
            sb.append(arr[i]).append("\n");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

 

예제 출력을 잘 살펴보면,

 

1. 처음 3줄이 규칙성을 가지고 반복된다. 

2. k가 1씩 커질 때마다 전체 라인 수는 2배로 늘어난다.

라는 사실을 알 수 있다.

 

총 n개의 줄을 [0]~[n-1] 에 채워야 한다고 할 때,

 

1. 위쪽 절반(0 ~ (n-1)/2) 은 이전 단계에서 양 옆에 공백을 전체 라인의 절반((n-1)/2)만큼 달아주면 된다.

2. 아래쪽 절반은 위쪽절반이 공백 하나를 사이에 두고 양 옆에 대칭으로 위치한 모양이 되어야 한다.

이는 [i] = [i - 총 라인 수의 절반]  + " " + [i - 총 라인 수의 절반] 으로 나타낼 수 있다.