Node.js) 백준 1106번: 호텔

http://boj.ma/1106/t

1106번: 호텔

 

앞으로 풀고 나서 학생들한테 설명할 수 있을만큼 풀이를 작성해봐야겠다.

 

 

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

const dp = new Array(1101).fill(Infinity);
dp[0] = 0;
input.forEach((v) => {
    const [cost, man] = v;
    for (let i = man; i < 1101; i++) {
        dp[i] = Math.min(dp[i - man] + cost, dp[i]);
    }
});

console.log(Math.min(...dp.splice(C)));

 

 

이 문제는 배낭문제 같은건데. 아무튼 배낭문제 느낌이야

 

dp[i] 는 i 만큼의 고객을 유치하는데 드는 최소 비용 이다.

 

dp문제는 초기상태라고 해야할까. dp배열의 초기값이랑 사이즈를 생각해봐야하는데

배열의 크기를 얼마로 정할지도 좀 생각해봐야하는데 그냥 대충 C의 최대가 1000이고 

고객이 100보다 작다고 하니까 대충 1101 로 배열 크기를 정해주고 순회했다.

 

그동안 dp 문제를 풀었던 경험으로 점화식 고민 없이 푼 문제라 뭐라고 설명하기가 어렵네 

 

그동안 딸랑 코드만 올리고 끝냈는데, 잘 설명하는 방법을 다른 블로그 보고 배워봐야겠다. 

처음 보는 사람도 딱 이해할 수 있게 설명하는