백준(1149)_dp.md

백준(1149)_dp

---

const fs = require('fs');
const stdin = (process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `3
26 40 83
49 60 57
13 89 99`
).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const N = parseInt(input())
let cost = []
let dp = Array.from(Array(N + 1), () => Array(3))
cost.push(new Array(N).fill(0))
for (let i = 0; i < N; i++) {
    cost.push(input().split(' ').map((A) => parseInt(A)))
}

dp[0][0] = dp[0][1] = dp[0][2] = 0;
for (let i = 1; i <= N; i++) {
    dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
    dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
}
let ans = Math.min(Math.min(dp[N][0], dp[N][1]), dp[N][2]);
console.log(ans)

dp문제.

가장 기본적인 아이디어는 선택할 수 있는 두가지의 선택지 중 더 비용이 적은 것을 선택해나간다는 것이다.

0	0	0

처음 이와 같은 dp 테이블을 만들어놓고 시작한다. 한 개 행 위에서 선택할 수 있는 두 지점 중 더 작은 비용을 선택하고 그 비용에 자신의 비용을 더해나가는 식이다. 그렇게 끝까지 돌게되면 다음과 같은 테이블이 만들어진다.

0	0	0
26	40	83
89	86	83
96	83 + 89	99 + 86