[BOJ/Step10] 2447 : 별 찍기 - 10 (JAVA)

www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

---

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***

*  *

***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

 

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

 

출력

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

 

예제 입력 1

27

 

예제 출력 1

 

---

풀이

( 아니 문제에는 N=3k이며, 이때 1 ≤ k < 8 이라고 나와서 1이 입력되는 거는 전혀 생각도 안하고 고려도 안했는데 뭐 어떤 방법을 써도 계속 시간초과가 나서 뭐지 하고 찾아봤더니 1이 입력되면 별 하나가 출력되야 한다고 한다.... 그래서 그것만 추가해주었더니 시간초과 없이 정답... 너무 화난다... )

n은 3의 배수로 입력되고, n*n 크기의 사각형으로 *이 출력된다.

전체 사각형을 9개로 나눴을 때, 정 가운데는 항상 빈칸, 나머지 8개 부분은 또 9개로 나눠져 같은 규칙을 반복한다 => 재귀함수

 

처음에는 한줄한줄 순서대로 출력하는 걸 생각했는데 그런 방법은 도저히 떠오르지 않았다. n*n크기의 2차원 배열을 만들어 *과 공백을 입력하는게 낫겠다 싶었다

 

가장 작은 범위는 n이 3일 때 노란색 네모 부분처럼 출력될 때이다 : 최소 사각형

 

void Star(String[][] star, int n, int x, int y)

배열 star와 n, 왼쪽 꼭대기의 좌표가 입력되면 해당 위치에 최소 사각형을 저장

   1. n == 3 의 조건을 만족할 때 해당 위치에 최소 사각형을 저장,

   2. n != 3 이면 n/3와 변경된 x, y를 매개변수로 재호출한다.

 

void Blank(String[][] star, int n, int x, int y)

배열과 n, 왼쪽 꼭대기의 좌표가 입력되면 해당 위치에 n*n 크기의 공백을 저장

 

 

1. n이 입력되면 Star(star, n, 0, 0)을 호출

2. Star 내부에서 n == 3 인지 검사, 3이 아니라면 n/3 크기의 Star을 재호출해야 하는데 총 9부분으로 쪼개지기 때문에 n/3 크기의 사각형을 9번 호출해야 한다.

또, 5번째 사각형은 모두 공백이어야 하기 때문에 conut변수를 따로 선언해서 count가 5일때는 Blank 함수를, 그 외에는 Star 함수를 호출해준다.

9번 호출시 x,y를 (0, 0) , (0, n/3) , (0, 2n/3) , (n/3, 0) , (n/3, n/3) , (n/3, 2n/3) , (2n/3, 0) , (2n/3, n/3) , (2n/3, 2n/3)으로 호출해야 하기 때문에 for문의 조건을 for(int i = x; i < x + n; i += n/3) / for(int j = y; j < y + n; j += n/3) 로 작성한다.

 

재귀호출

 

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

public class B2447 {
	
	static void Star(String[][] star, int n, int x, int y) {
		if(n == 3) {
			for(int i = x; i < x+3; i ++) {
				for(int j = y; j < y+3; j ++) {
					star[i][j] = "*";
				}
			}
			star[x+1][y+1] = " ";
		} else {
			int count = 1;
			for(int i = x; i < x + n; i += n/3) {
				for(int j = y; j < y + n; j += n/3) {
					if(count == 5) {
						Blank(star, n/3, i, j);
					} else {
						Star(star, n/3, i, j);
					}
					count++;
				}
			}
		}	
	}
	
	static void Blank(String[][] star, int n, int x, int y) {
		for(int i = x; i < x + n; i ++) {
			for(int j = y; j < y + n; j ++) {
				star[i][j] = " ";
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = sc.nextInt();
		if(n == 1) {
			System.out.println("*");
			return;
		}
		
		String[][] star = new String[n][n];
		
		Star(star, n, 0, 0);		
			
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < n; j ++) {
				bw.write(star[i][j]);
			}
			bw.newLine();
		}
		bw.flush();
	}
}