[Baekjoon]2448번 별 찍기 - 11

2448번: 별 찍기 - 11 (acmicpc.net)

2448번: 별 찍기 - 11

 

 

이 문제는 유명한 별찍기 문제의 심화버전 중 하나이다. 수학적인 규칙이 존재하고 그걸 발견해서 구현하면 됐지만, 나 같은 경우 클래스를 활용해서 풀고 싶어졌다. 그래서 아래와 같은 코드를 짜고 설마 돌아가진 않겠지? 생각하며 돌렸는데...

 

 

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

public class Main{
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Fractal f = new Fractal(n);
        StringBuilder[] tea = f.makeStar(n);
        f.printBigStar(tea, n);
    }

    static class Fractal{
        Fractal top;
        Fractal left;
        Fractal right;
        int height;

        StringBuilder[] arr;

        public Fractal(int n){
            if(n == 3){
                arr = new StringBuilder[n];
                return;
            }
            top = new Fractal(n/2);
            left = new Fractal(n/2);
            right = new Fractal(n/2);
            height = n;
            arr = new StringBuilder[n];

        }

        public StringBuilder[] makeStar(int n) {
            if (n == 3) {
                arr[0] = new StringBuilder("  *  ");
                arr[1] = new StringBuilder(" * * ");
                arr[2] = new StringBuilder("*****");
                return arr;
            }
            StringBuilder[] resultSb = new StringBuilder[n];
            StringBuilder[] tb = top.makeStar(n / 2);
            StringBuilder[] lb = left.makeStar(n / 2);
            StringBuilder[] rb = right.makeStar(n / 2);

            StringBuilder temp;
            for(int j = 0; j < n / 2; j++){
                temp = new StringBuilder();
                for(int i = 0; i < n/2; i++){
                    temp.append(" ");
                }
                temp.append(tb[j]);
                for(int i = 0; i < n/2; i++){
                    temp.append(" ");
                }
                resultSb[j] = temp; //top triangle
            }
            int count = n/2;
            for(int i = 0 ; i < n/2; i++){
                StringBuilder sb = new StringBuilder();
                sb.append(lb[i]);
                sb.append(" ");
                sb.append(rb[i]);
                resultSb[count++] = sb;

            }

            return resultSb;
        }

        public void printBigStar(StringBuilder[] sb, int n){
            for(int i = 0; i < n; i++){
                System.out.println(sb[i]);
            }
        }
    }
}

 

 

 

통과가 됐다!

 

왜지? 아무튼 기쁘다. 메모리 한도인 256mb를 가까스로 초과하지 않았다. 다른 분들이 푸신 걸 보니 속도가 나보다 확연히 빠른 점을 봐선 아무래도 재귀나 반복 등 수학을 활용한 효율적인 풀이가 존재하는 거 같다.

 

큰 기대는 안했는데 통과돼서 기쁘다..!