🎲 백준 1106번 호텔 [JS]

🧶 풀이

• dp[i]는 i명 일 때 최소비용
• 각 도시마다 dp 값을 업데이트 한다.
  -dp[people(얻을 수 있는 고객의 수)] > 홍보비용 이면 dp값 업데이트
  -dp[1] 부터 dp[C]까지 dp 인덱스가 people 보다 작다면 dp[i], 홍보비용중 작은 값으로 업데이트, 아니라면 dp[i], dp[people] + dp[i - people]로 업데이트 하며 dp[C]값을 구해준다.

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));
const [C, N] = input.shift();

const dp = new Array(C + 1).fill(Infinity);
dp[0] = 0;

for (let [cost, people] of input) {
  if (dp[people] > cost) dp[people] = cost;
  for (let i = 1; i <= C; i++) {
    dp[i] =
      i < people
        ? Math.min(dp[i], cost)
        : Math.min(dp[i], dp[people] + dp[i - people]);
  }
}

console.log(dp[C]);

🎨 참고 코드