[백준 4779] 칸토어 집합 (Node.js) - 분할정복

문제 링크

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

4779번: 칸토어 집합

---

답안

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "text.txt";
const newLine = process.platform === "linux" ? "\n" : "\r\n";
const input = fs.readFileSync(filePath).toString().trim().split(newLine).map(Number);

const cantor = (num) => {
  let divide = Math.floor(num / 3);
  if (divide === 0) return "-";
  let space = "";
  for (let i = divide; i < divide * 2; i++) {
    space += " ";
  }
  return `${cantor(divide)}${space}${cantor(divide)}`;
};

function solution(input) {
  let answer = "";
  for (let number of input) {
    let num = Math.pow(3, number);
    answer += `${cantor(num)}\n`;
  }
  return answer;
}

console.log(solution(input).trim());

 

해설

분할정복 문제

• 문제의 예시를 보면 같은 비율로 공백과 문자열(-)이 쪼개지고 있음을 알 수 있다.
• -의 길이가 27개인 문자열의 경우, ---------        --------- 이 된다. - 9개, 공백 9개, - 9개로 이루어져 있다.
• -의 길이가 9개인 문자열의 경우, ---   --- 이 된다. - 3개, 공백 3개, - 3개로 이루어져 있다.
• -의 길이가 3개인 문자열의 경우, - - 이 된다. - 1개, 공백 1개, - 1개로 이루어져 있다.

좌 우측을 1/3 씩 분할정복 하면서 가운데 1/3은 공백으로 남겨두면 해결되는 문제이다.