백준 2778 < 별 찍기 - 11 > JavaScript

📍문제 링크

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

2448번: 별 찍기 - 11

 

📍알고리즘 분류

- 재귀

 

📍문제 풀이

- N = 3 * 2^k 형태로 주어질 때, (k = 음이 아닌 정수) 별을 찍어라

 

분할정복을 사용하는 어려운 별 찍기 문제

 

/*
N = 3 * 2^k (k = 0.. 1.. )

k = 0
N = 3

   *
  * *
 *****

col = 2 * N - 1 = 5
row = N = 3
-------------------------
k = 1
N = 6

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

col = 2 * N - 1 = 11
row = N = 6
-------------------------

N = 6 일때를 잘 살펴보면
  1
2  3
처럼 삼각형이 배치된다

tree 배열
- 최소 별 모양을 가진 string[]

star 함수
- 시작지점 (좌상단)을 입력받아 base case에서 tree 모양을 그림
- base case 가 아니면 매개변수 분할하여 재귀 호출

 */

 

N = 3 (k = 0) 일 때 삼각형

 

N = 6 (k = 1) 일 때 삼각형

 

여기서 만들어야 할 시작 지점을 어떻게 분할할지 알 수 있다

 

width = 2 * N - 1
height = N

star(num, row, column)

=>
star(6, 0, 0)

 

- 분할 - 

star(num / 2, row, col + num / 2)
star(num / 2, row + num / 2, col)
star(num / 2, row + num / 2, col + num)

=>
star(3, 0, 0 + 3)
star(3, 0 + 3, 0)
star(3, 0 + 3, 0 + 6)

 

N = 12 (k = 2)

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = 0;

rl.on("line", (line) => {
  input = +line;
}).on("close", () => {
  const tree = ["  *  ", " * * ", "*****"];
  const answer = Array.from({ length: input }, (_) =>
    Array.from({ length: 2 * input - 1 }, (_) => " "),
  );
  const star = (num, row, col) => {
    // base case num = 3
    if (num === 3) {
      for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 5; j++) {
          answer[row + i][col + j] = tree[i][j];
        }
      }
      return;
    }

    star(num / 2, row, col + num / 2);
    star(num / 2, row + num / 2, col);
    star(num / 2, row + num / 2, col + num);
  };
  star(input, 0, 0);
  console.log(answer.map((row) => row.join("")).join("\n"));
});