문제

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

문제 분석

→ dp

function run(inputs: string) {
  // f(n) = min(f(n-3) , f(n-5)) +1
  const n = Number(inputs);
  const memo = Array(n + 1).fill(-1);

  function go(num: number): number {
    if (num < 0) return Number.MAX_SAFE_INTEGER;
    if (num === 0) return 0;
    if (memo[num] !== -1) return memo[num];

    memo[num] = Math.min(go(num - 3), go(num - 5)) + 1;
    return memo[num];
  }

  const result = go(n);
  return result >= Number.MAX_SAFE_INTEGER ? -1 : result;
}