[백준] 2448 별 찍기 - 11 (자바/Java) 재귀, 분할정복

728x90

문제 링크

성능 요약

메모리: 236216 KB, 시간: 528 ms

분류

분할 정복(divide_and_conquer), 재귀(recursion)

문제 설명

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

입력

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

출력

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

분할정복이 아직 익숙하지 않은 것 같다... 하하 일단 내 힘으로는 재귀로 풀었다

크기가 3일 때부터 차례대로 채워가는 식으로 구현하였다.

재귀 풀이

		if (idx == N)
			return;

		if (idx == 0) {
			stars[0][N] = '*';
			stars[1][N - 1] = '*';
			stars[1][N + 1] = '*';
			for (int i = 0; i <= 2; i++) {
				stars[2][N - i] = '*';
				stars[2][N + i] = '*';
			}
			star(3);
		}

함수의 idx를 0부터 시작해서 증가시켜준다.

시작인 0일 때에는 해당 위치를 채운다.

가장 위의 삼각형은 col의 개수가 2*N인 배열에서 N부터 시작하기 때문에 N을 가운데에 두고 채우면 된다.

		else {
			for (int i = idx; i < idx * 2; i++) {
				for (int start = N - idx + 1; start <= N + idx - 1; start++) {
					stars[i][start - idx] = stars[i - idx][start];
					stars[i][start + idx] = stars[i - idx][start];
				}
			}
			star(idx * 2);
		}

그리고 0이 아닐 때에는 idx를 2배씩 늘려주며 재귀를 반복한다.

배열을 채우는 과정은 자신보다 위에 있는 배열을 복사하는 과정이다.

idx가 i일 때, 0~i에 있는 모양은 i~2*i까지 두 번 대칭으로 나온다.

역시 N을 가운데에 두고 왼쪽과 오른쪽에 값을 복사하였다.

전체 코드

그리고 이렇게 하면 삼각형의 맨 앞에 공백이 생기는데, 출력을 1부터 해주었다.

가운데 index를 N으로 하는 게 편해서 수정하는 것보다는 출력을 바꾸는 걸 선택했다

package Gold.g4;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ_2448_별찍기11 {
	static int N;
	static int K;

	static char[][] stars;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		stars = new char[N][2 * N];
		for (char[] ch : stars) {
			Arrays.fill(ch, ' ');
		}

		star(0);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			for (int j = 1; j < 2 * N; j++)
				sb.append(stars[i][j]);
			sb.append("\n");
		}
		System.out.print(sb);

	}

	static void star(int idx) {
		if (idx == N)
			return;

		if (idx == 0) {
			stars[0][N] = '*';
			stars[1][N - 1] = '*';
			stars[1][N + 1] = '*';
			for (int i = 0; i <= 2; i++) {
				stars[2][N - i] = '*';
				stars[2][N + i] = '*';
			}
			star(3);
		} else {
			for (int i = idx; i < idx * 2; i++) {
				for (int start = N - idx + 1; start <= N + idx - 1; start++) {
					stars[i][start - idx] = stars[i - idx][start];
					stars[i][start + idx] = stars[i - idx][start];
				}
			}
			star(idx * 2);
		}

	}

}

분할 정복 풀이

분할 정복도 비슷하긴 하지만, 조금 더 깔끔한 풀이인 것 같다.

먼저 각 함수에서 size를 선언한다. size가 3일 때에 별을 채우는 식이다.

재귀 풀이에서도 확인했듯이 같은 구조가 정가운데를 기준으로 대칭으로 하며 반복된다.

아래 사진에서 노란색 사각형 3개의 구조가 반복되는 것을 확인할 수 있다.

또 노란색 사각형 3개는 하나의 파란색 사각형이 되어 다시 구조를 반복한다.

삼각형의 가장 위의 가운데 좌표를 row, col로 둔다면 반복되는 구조는

row, col

row-size, col-size

row-size, col+size

이다.

그러므로 함수를 다음과 같이 구성할 수 있다.

	static void star(int row, int col, int size) {
		if (size == 3) {
			stars[row][col] = '*';
			stars[row + 1][col - 1] = stars[row + 1][col + 1] = '*';
			for (int i = 0; i <= 2; i++) {
				stars[row + 2][col - i] = '*';
				stars[row + 2][col + i] = '*';
			}
			return;
		}

		size /= 2;
		star(row, col, size);
		star(row + size, col + size, size);
		star(row + size, col - size, size);
	}