솜이의 데브로그

백준 2448번 ) 별 찍기 11 (java) 본문

Algorithm/백준

백준 2448번 ) 별 찍기 11 (java)

somsoming 2022. 8. 1. 02:27

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

 

2448번: 별 찍기 - 11

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

www.acmicpc.net

 

문제

높이 N이 주어질 때 위 모양 만들기

 

풀이

재귀적으로 파악하여 높이 N이 들어왔을 때 N-2 의 높이만큼 삼각형이 반복되는것을 확인한다.

전체 삼각형의 넓이는 2*N-1 이고, 이 역시 재귀적으로 N/2 씩 하며 삼각형이 생기는 것을 파악한다.

마지막으로 이 재귀함수가 언제 종료되는지 확인한다. 높이가 3일때가 가장 작은 삼각형이므로, 이 때 별을 찍고 재귀적으로 호출하는 것을 종료한다.

 

참고로 System.out.print 를 썼을 때 자꾸 시간초과가돼서 BufferedWriter를 사용해서 풀이해야했다.

 

코드

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

public class BOJ_2448 {
    private static char[][] map;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        map = new char[N][2*N-1];
        for(int i=0; i<N; i++){
            for(int j=0; j<2*N-1; j++){
                map[i][j] = ' ';
            }
        }

        drawStar(0, N-1, N);

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

    public static void drawStar(int x, int y, int n){
        if(n==3){
            map[x][y] = '*';
            map[x+1][y-1] = map[x+1][y+1] = '*';
            map[x+2][y-2] = map[x+2][y-1] = map[x+2][y] = map[x+2][y+1] = map[x+2][y+2] = '*';
            return;
        }

        drawStar(x, y, n/2);
        drawStar(x + n/2, y - n/2, n/2);
        drawStar(x + n/2, y + n/2, n/2);
    }
    
}

'Algorithm > 백준' 카테고리의 다른 글

백준 1107번 ) 리모컨 (java)  (0) 2022.08.01
백준 1253번 ) 좋다 (java)  (0) 2022.08.01
백준 2293번 ) 동전 1 (java)  (0) 2022.07.23
백준 10026번 ) 적록색약 (java)  (0) 2022.07.23
백준 12931번 ) 두 배 더하기 (java)  (0) 2022.07.22