📍 출처
출처 : https://www.acmicpc.net/problem/2447
📝 문제
재귀적인 패턴으로 별을 찍어 보자. 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번째 줄까지 별을 출력한다.
⌨️ 예제 입력
27
🖨 예제 출력
📚 내가 제출한 코드
import java.util.Scanner;
public class Main {
static char[][] arr;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
arr = new char[N][N];
star(0,0,N,false);
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < N ; i++){
for(int j = 0 ; j < N ; j++){
sb.append(arr[i][j]);
}
sb.append("\n");
}
System.out.print(sb);
}
public static void star(int x, int y, int N , boolean blank){
//blank : true 공백
if(blank){
for(int i = x ; i < x + N ; i++){
for(int j = y ; j < y + N ; j++){
arr[i][j] = ' ';
}
}
return;
}
// 더이상 쪼갤 수 없는 블록일 때
if(N == 1){
arr[x][y] = '*';
return;
}
int size = N/3;
int count = 0;
/*
N=27 일 경우 한 블록의 사이즈는 9이고,
N=9 일 경우 한 블록의 사이즈는 3이듯
해당 블록의 한 칸을 담을 변수를 의미 size
count는 별 출력 누적을 의미
*/
for(int i = x ; i < x + N; i += size){
for(int j = y ; j < y + N ; j += size){
count++;
if(count == 5){
star(i,j,size,true);
}else{
star(i,j,size,false);
}
}
}
}
}✏️ 내가 제출한 코드에 대한 설명
숫자를 3, 9, 27순으로 입력하면 다음과 같은 그림이 나와야 한다.
그림을 보면 가로, 세로가 입력한 숫자만큼 길이를 갖고 각 그림을 9개의 블록으로 나눌 수 있다.
여기서 27을 9등분한 후 하나의 블록을 보면 9개짜리 모양이 되고 9개짜리를 나누면 3개짜리가 되는 것을 알 수 있다. 여기서 우리는 재귀를 사용하여 문제를 해결할 수 있다는 것을 알 수 있다.
즉 만약 27이 입력되었다면 9등분하고 나온 블록을 다시 9등분하여 분할정복식으로 문제를 해결하는 것이다.
그림을 보다시피 가로세로가 있기때문에 2차원 배열을 사용하여 문제를 해결하였다.
또한 여기서 공백의 규칙을 알아야한다. 공백의 경우 그림을 9등분 하였을 때 가운데 부분이다.
즉, 각 단계에서 9칸으로 구분 한 뒤, x, y 좌표에 따라서 공백 또는 재귀 호출을 반복해주어 더 이상 나눌 칸이 없을 때까지 반복하는 것이다.
