[백준 1351] 무한 수열 (Hash/DFS, 자바스크립트)

무한 수열

문제

무한 수열 A는 다음과 같다.

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)
  N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력
첫째 줄에 AN을 출력한다.

제한

• 0 ≤ N ≤ 1012
• 2 ≤ P, Q ≤ 109

풀이

dictionary 자료구조를 이용하여 풀 수 있는 문제이다.

dfs(n)을 호출하여 AN을 구하는데,

함수 안에서 dict[i] = dfs(Math.floor(i/p)) + dfs(Math.floor(i/q)) 로 dict에 필요한 값들을 채우고 마지막에 dict[n]을 반환한다.

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [n, p, q] = require("fs").readFileSync(filePath).toString().trim().split(" ").map(Number);

const dict = {}
dict[0] = 1

function dfs(i) {
    if (i in dict) return dict[i];

    return dict[i] = dfs(Math.floor(i/p)) + dfs(Math.floor(i/q));
}

console.log(dfs(n));