[BaekJoon] 1351 번 무한 수열 문제 - (nodejs)

문제 번호 :  1351 번

문제 바로가기 ☞ https://www.acmicpc.net/problem/1351

---

 

<<< 문제 내용 >>>

---

 

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

let [N, P, Q] = input[0].split(" ").map(Number);

let savedArr = {};
savedArr[0] = 1;

const solution = (index) => {
  if (index < 0) {
    return;
  }

  const left = Math.floor(index / P);
  const right = Math.floor(index / Q);
  let first = 0;
  let second = 0;

  if (left in savedArr) {
    first = savedArr[left];
  } else first = solution(left);

  if (right in savedArr) {
    second = savedArr[right];
  } else second = solution(right);

  savedArr[index] = first + second;
  return savedArr[index];
};

if (N !== 0) solution(N);

console.log(savedArr[N]);

* N을 0까지 차례대로 올라가면서 재귀로 값을 구해주는 문제였다.

만약 이전에 구했던 값이 있다면, 저장해두어서 한번 더 재귀가 돌아가지 않게 해주는게 핵심 포인트이다.

로직 자체는 매우 심플하였다.

처음엔 N이 10^12를 고려하지 못하고 배열을 N만큼 만들어서 저장했었는데 RangeError 가 뜨길래 아!

하고 딕셔너리로 변경하였다.

 

이 문제는 친절하게도 쉽게 생각해서 놓칠 N이 0일 때의 케이스를 테스트케이스에서 물어준다.

 

솔직히 이 문제는 실버 3정도의 문제 같은데 왜 골드 4 문제일까..?

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.