문제

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

문제 분석

• n kg의 설탕을 최소한의 봉지 개수로 나누는 것이 목표(n kg을 최소한의 봉지 개수로 나누는 방법)
• n kg를 나누려면
  • 3kg 봉지 하나를 더 사용해서 나누는 방법 (n - 3kg에서 시작)
  • 5kg 봉지를 하나 더 사용해서 나누는 방법 (n - 5kg에서 시작)
• 즉, n kg을 최소 봉지 개수로 나누는 문제 f(n)는 다음과 같이 작은 문제로 나눌 수 있다.
  • f(n-3): n kg에서 3kg을 뺀 후 남은 무게를 나누는 최소 봉지 개수
  • f(n-5) n kg에서 5kg을 뺀 후 남은 무게를 나누는 최소 봉지 개수
  • 더 작은 값을 선택 해야 최소 봉지 개수
  • f(n) = min(f(n-3), f(n-5)) + 1

→ 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;
}

• 중복 계산이 이루어지지 않아 각 값에 대해 최대 한 번만 계산이 발생됨
• n-3 이나 n-5로 줄어드는 과정에서 모든 값이 계산된다고 가정하면(최악의 경우) 재귀 호출의 깊이는 n과 비례한다. → 재귀 호출의 최대 깊이는 n
• 따라서 시간 복잡도는 O(n)