https://www.acmicpc.net/problem/2839
n kg
의 설탕을 최소한의 봉지 개수로 나누는 것이 목표(n kg
을 최소한의 봉지 개수로 나누는 방법)n kg
를 나누려면
n kg
에서 3kg을 뺀 후 남은 무게를 나누는 최소 봉지 개수n kg
에서 5kg을 뺀 후 남은 무게를 나누는 최소 봉지 개수→ 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;
}