백준[nodejs] > 9465번 스티커

 

문제링크

https://www.acmicpc.net/problem/9465

 

풀이

처음에는 dp(다이나믹 프로그래밍) 을 생각하지 못하여 고전했다.

여기서 map은 스티커들의 배열을 의미하고

 

dp[0][i] 는 첫번째줄의 i+1번째 스티커 사용했을 때 가질 수 있는 최대 총점

dp[1][i] 는 두번째줄의 i+1번째 스티커를 사용했을 가질 수 있는 최대 총점

dp[2][i] 는 i+1번째의 스티커 어느것도 사용하지 않았을 때 가질 수 있는 최대 총점 이다. 

 

dp[0][0] dp[1][0] dp[2][0] 부터 마지막 열까지 진행하면 나올 수 있는 최대 점수들을(dp[0][n-1], dp[1][n-1], dp[2][n-1]) 구할 수 있고 dp[0][n-1], dp[1][n-1], dp[2][n-1] 값중 최댓 값이 답이 된다.

 

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let [caseCnt, ...arr] = input;

for (let i = 0; i < arr.length; i += 3) {
    let n = Number(arr[i]);

    let map = [];

    map.push(arr[i + 1].split(" ").map((num) => Number(num)));
    map.push(arr[i + 2].split(" ").map((num) => Number(num)));

    let dp = Array.from({ length: 3 }, () => {
        return Array(n).fill(0);
    });

    dp[0][0] = map[0][0];
    dp[1][0] = map[1][0];
    dp[2][0] = 0;

    for (let j = 1; j < n; ++j) {
        dp[0][j] = map[0][j] + Math.max(dp[1][j - 1], dp[2][j - 1]);
        dp[1][j] = map[1][j] + Math.max(dp[0][j - 1], dp[2][j - 1]);
        dp[2][j] = Math.max(dp[0][j - 1], dp[1][j - 1]);
    }

    let max = Math.max(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]);
    console.log(max);
}