BOJ 2579
const stdin =
process.platform === "linux"
? require("fs").readFileSync("/dev/stdin")
: `6
10
20
15
25
10
20`;
const input = stdin.toString().trim().split("\n");
let [N, ...arr] = input;
arr = arr.map(v => +v)
N = +N;
const dp = new Array(N).fill(0);
dp[0] = arr[0];
dp[1] = Math.max(arr[0] + arr[1], arr[1])
dp[2] = Math.max(arr[0] + arr[2], arr[1] + arr[2])
for(let i=3; i<N; i++) {
dp[i] = Math.max(arr[i] + arr[i-1] + dp[i-3], arr[i] + dp[i-2])
}
console.log(dp[N-1]);
// DP
전형적인 DP문제로 1층, 2층, 3층까지 갈 수 있는 최대값을 구한 후 그 이후에 값을 이전의 dp 값을 활용하여 구해낸다.
DP로 푼다는 것을 아는것이 중요하겠다..
Author And Source
이 문제에 관하여(BOJ 2579), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@scato/BOJ-2579저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)