[JavaScript] 백준 재귀 #2447번 별 찍기 - 10

https://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

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

 

 

전체 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();

let star = '';

function printStar(i, j, num){
    if(i%3 === 1 && j%3 ===1){
        star+=' ';
    } else{
        if(num == 1){
            star += '*'
        } else {
            printStar(parseInt(i/3), parseInt(j/3), parseInt(num/3));
        }
    }

}

function onStar(n){
    for(let i=0; i<input; i++){
        for(let j=0; j<input; j++){
            printStar(i, j, n);
        }
        star += '\n';
    }
}

onStar(input);
console.log(star);

 

 

 

해결 방법

문제를 읽어도 도통 무슨 소리인지 몰라서 다른 블로그 글을 참고했다. 여러 풀이를 봐도 이해가 안돼서 손으로 하나씩 써보면서 이해했다.

 

N = 3이라고 생각해보자.

	0	1	2
0	*	*	*
1	*		*
2	*	*	*

N이 3일 경우 3x3의 정사각형이 생기고 가운데에 공백이 생긴다. 즉, (1, 1)이 공백인 것이다. 

이 사각형이 두 개가 있다고 생각하면,

	0	1	2	3	4	5
0	*	*	*	*	*	*
1	*		*	*		*
2	*	*	*	*	*	*

이렇게 (1, 1), (1, 4)에 공백이 생긴다. 옆으로 하나 더 사각형이 생긴다면? (1, 7)에 공백이 생긴다.

사각형을 아래로 붙여도 마찬가지이다. (4, 1), (7, 1).. 이런 식으로 공백이 생길 것이다.

 

즉, ( i  % 3 ===1, j % 3 === 1)로 두 수 모두 3으로 나눴을 때 나머지가 1인 경우에 공백이 생기는 것이다.

 

그리고 우리가 고려해야 할 두 번째 공백 규칙이 있다. N이 3보다 클 경우 (N/3, N/3)에서 (N/3) x (N/3) 크기의 공백이 생긴다는 것이다. 

 

만약 N = 9 인 경우

	0	1	2	3	4	5	6	7	8
0	*	*	*	*	*	*	*	*	*
1	*		*	*		*	*		*
2	*	*	*	*	*	*	*	*	*
3	*	*	*				*	*	*
4	*		*				*		*
5	*	*	*				*	*	*
6	*	*	*	*	*	*	*	*	*
7	*		*	*		*	*		*
8	*	*	*	*	*	*	*	*	*

이렇게 공백이 생긴다.  (9/3)=3, (3, 3)에서 3x3크기만큼 공백이 생기는 것. 

(3, 4), (3, 5), (3, 6), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5) 부분인데 두 수 모두 3보단 크되 6을 넘지 않는 것을 알 수 있다. 

즉, 3으로 나눴을 때 몫이 1.xx인 것!

 

따라서 재귀 함수를 사용해서 값들을 다 3으로 나눠줄 것이다. 왜냐하면 몫이 1.xx인지 아닌지 확인해서 공백을 줄지 별표를 줄지 정해야하기 때문에!

 

 printStar(parseInt(i/3), parseInt(j/3), parseInt(num/3))의 예시를 살펴보자.

 

만약 i=2, j=3, num=9라고 하자.

pinrtStar( parseInt(2 / 3) = 0, parseInt(3 / 3) = 1, parseInt(9 / 3) = 3 )이다.

i와 j 둘 다 나머지가 1도 아니고 num이 1도 아니기 때문에 다시 함수를 호출한다.

pinrtStar( parseInt(0 / 3) = 0, parseInt(1 / 3) = 0, parseInt(3 / 3) = 1 )이면 num이 1이기 때문에 별이 찍힌다.

 

만약 i=3, j=5, num=9라고 하자.

pinrtStar( parseInt(3 / 3) = 1, parseInt(5 / 3) = 1, parseInt(9 / 3) = 3 )이다.

i와 j가 모두 3으로 나눴을 때 나머지가 1이기 때문에 공백이 찍힌다.

 

따라서 재귀 함수는

printStar (3, 3, 9) = printStar(1, 1, 3) => 공백

printStar (2, 6, 9) = printStar(0, 2, 3) = printStar(0, 0, 1)  => *

 

이런 식으로 작동하는 것이다.

 

 

 

참고 사이트

https://chunghyup.tistory.com/68

[알고리즘] 백준 - 2447 별 찍기 - 10 해설, node js 구현