문제 링크

성능 요약

메모리: 36836 KB, 시간: 664 ms

분류

재귀

제출 일자

2024년 12월 25일 00:09:03

문제 설명

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

입력

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

출력

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

풀이

느낀점

• 출력 연습도 해야 하는구나.. 집중할 시간이 부족해서 틈틈이 하다보니 규칙을 찾아 출력하는게 꽤나 오래걸렸다.

설계 : 60분

• 입력된 N의 값에 따라 3*2^k 의 형태로 규칙을 정리, 2^k 값 필요
• 전체 출력크기를 boolean[][] star 배열로 생성, 별을 찍은 위치를 true로 기록
• k 가 1 이상일때, 큰 삼각형을 기준으로 위아래를 반으로 나누면 위의 작은 삼각형이 아래에 양쪽으로 동일하게 출력됨을 알 수 있음.
• 아래 양쪽 삼각형의 출력기준을 위 삼각형으로 삼을 때 좌표 차이는 3*2^(k-1) 만큼 적절히 이동하면 복사 가능
• 가장 작은 삼각형을 먼저 star 배열에 기록한 후 이를 기준으로 k번 반복하며 범위를 넓히고 기록 및 출력

코드(Java)

• 구현 시간: 90분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 별 찍기 - 11_2448
 * Date: 2024.12.24
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static boolean[][] star;

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

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int m = n / 3;
        int k = (int) (Math.log(m) / Math.log(2));

        int col = (m * 5) + (m - 1);
        star = new boolean[n][col];
        star[0][col / 2] = star[1][col / 2 - 1] = star[1][col / 2 + 1] = true;
        for (int i = col / 2 - 2; i <= col / 2 + 2; i++) {
            star[2][i] = true;
        }

        int start = col / 2 - 2;
        int end = col / 2 + 2;
        for (int i = 0; i <= k; i++) {
            if (i == 0) {
                for (int j = 0; j < 3; j++) {
                    for (int c = 0; c < col; c++){
                        if (star[j][c]) bw.write("*");
                        else bw.write(" ");
                    }
                    bw.write("\n");
                }
            } else {
                int gap = (int) Math.pow(2, i - 1) * 3;
                start -= gap;
                end += gap;

                for (int j = gap; j < Math.pow(2, i) * 3; j++) {
                    for (int c = 0; c < col; c++) {
                        if (c == col / 2) bw.write(" ");
                        else if (c >= start && c < col / 2) {
                            if (star[j-gap][c+gap]) {
                                star[j][c] = true;
                                bw.write("*");
                            } else bw.write(" ");
                        } else if (c > col / 2 && c <= end) {
                            if (star[j-gap][c-gap]) {
                                star[j][c] = true;
                                bw.write("*");
                            } else bw.write(" ");
                        } else bw.write(" ");
                    }
                    bw.write("\n");
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}