[백준-2502] 떡 먹는 호랑이 | node.js | silver1

문제

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

2502번: 떡 먹는 호랑이

 

풀이

function solve() {
  const aDp = [1, 0];
  const bDp = [0, 1];

  for (let i = 2; i < d; i++) {
    aDp[i] = aDp[i - 1] + aDp[i - 2];
    bDp[i] = bDp[i - 1] + bDp[i - 2];
  }
  const aCoef = aDp[d - 1];
  const bCoef = bDp[d - 1];

  for (let i = 1; i <= k; i++) {
    const remain = k - aCoef * i;
    if (remain % bCoef === 0) {
      console.log(`${i}\n${remain / bCoef}`);
      break;
    }
  }
}

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "백준/silver/2502/testcase.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");
let [d, k] = input[0].split(" ").map((el) => +el);
solve();

 

이 문제는 그냥 수학식이다.
처음 두 값이 A, B니까 두번째 값은 A+B, 세번째 값은 B+A+B => A+2B, 네번째 값은 2A+3B, 다섯번째 값은 3A+5B •••

이 로직을 dp를 이용해서 구하면 마지막 D번째에 오는 숫자들이 각각 A와 B의 계수가 될 것이다. 그럼 여기서부터 A값에 1부터 쭉 대입해보면서 B값이 올바른 정수로 나올 경우 답을 출력하고 break로 종료하면 끝!