[JAVA] BOJ(백준) - 별 찍기 11 - 2448

문제내용

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

2448번: 별 찍기 - 11

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

입력

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

출력

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

---

문제 접근 방법

분할 정복 알고리즘으로 풀어야하는 문제다. 따라서 재귀를 사용해야 하는 문제이고 DP문제를 풀때처럼 어느정도의 점화식을 세울줄 알아야한다. 먼저 규칙을 살펴보자.

 

규칙

1. 2차원 배열의 크기는 Nx(2N-1) 이 된다.
2. k가 0일때 최소 트리가 된다. 즉, 입력받은수가 3일때 최소트리이고 이는 1행에 별 한개 / 2행에 별 두개 / 3행에 별 다섯개 인 트리를 말한다.
3. k가 증가될 때마다 전에 있던 트리와 같은 모양으로 위쪽, 왼쪽, 오른쪽으로 트리가 생성된다.
   예를들어 k=1이면 k=0일때 트리가 위쪽, 왼쪽, 오른쪽으로 자리잡고 이는 k=1일때 하나의 트리가 된다는 말이다.

일단 이 3가지 규칙을 먼저 찾고 가야한다. 후에 입력 받은수를 2로 계속해서 n이 3으로 될때까지 나눠주면서 위쪽, 왼쪽, 오른쪽 중 어느쪽 트리인지 먼저 판단 후 n이 3일때 최소 트리를 찍어주는 작업이 필요하다.

즉, 이작업에서 재귀는 위쪽, 왼쪽, 오른쪽 트리를 하나씩 맡아서 나누는 역할을 하게된다.

 

코드를 보고 이해해보자.

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static char[][] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		arr = new char[N][(2*N)-1];
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr[i].length; j++) {
				arr[i][j]=' ';
			}
		}
		
		//별 채우기
		//fillStar(첫 행, 가운데 열, 가장 작은 값까지 나누기위한 것(입력받은수)) 
		fillStar(0,N-1,N);
		printStar();//출력
	}
	
	public static void fillStar(int r, int c, int n) {
		//각 트리가 가장 작은 값으로 됐을때 별찍기
		if(n==3) {
			arr[r][c]='*';//트리하나의 맨위의 별
			arr[r+1][c-1]=arr[r+1][c+1]='*';//가운데 별들
			arr[r+2][c-2]=arr[r+2][c-1]=arr[r+2][c]=arr[r+2][c+1]=arr[r+2][c+2]='*';//마지막 별들
			return;//종료
		}
		
		//가장 작은값(가장 작은트리가)이 아닐때 3*2의제곱수 이므로 2로 나눠줌.
		int size = n/2;
		fillStar(r, c, size);//모여있는 3개의 트리중 가장위쪽 트리 탐색
		fillStar(r+size, c-size, size);//3개의 트리중 아래왼쪽 트리 탐색
		fillStar(r+size, c+size, size);//3개의 트리중 아래오른쪽 트리 탐색
	}
	
	public static void printStar() {
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr[i].length; j++) {
				sb.append(arr[i][j]);
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
}

---

마치며

재귀를 활용해본 경험이 많다면 푸는데 어려움은 없을 것이라 생각한다. 물론 본인은 어려웠다.

또한 주의해야 할점은 별을 print하는 과정에서 StringBuilder에 객체에 담고 출력하는게 아니라 그때그때 표준 입출력을 사용하게되면 StringBuilder로 한번의 표준입출력을 사용하는 것보다 속도가 느리기때문에 시간초과가 나게된다는걸 주의하자.