[JS] 설탕배달 - 백준 2839

문제

시간복잡도

O(n)

 

해결방법

i는 (i-3)+ 3 또는 (i-5)+5 으로 만들 수 있다. 

3과 5로 만들 수 없는 경우에는 -1을 저장한다.

예외로 dp[i-3] 또는 dp[i-5]가 -1인 경우를 고려한다.

dp[i]=Math.min(dp[i-3],dp[i-5])

 

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./example.txt";
let input = fs.readFileSync(filePath).toString();
input = parseInt(input);

let dp = [0, -1, -1, 1, -1, 1];

for (let i = 6; i <= input; i++) {
  let a = dp[i - 3];
  let b = dp[i - 5];
  if (a == -1 && b == -1) {
    dp[i] = -1;
  } else if (a == -1) {
    dp[i] = b + 1;
  } else if (b == -1) {
    dp[i] = a + 1;
  } else {
    dp[i] = Math.min(a, b) + 1;
  }
}
console.log(dp[input]);