[백준] 14501 퇴사

첫번째 시도

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const arr = input.map(x => x.trim().split(' ').map(x=>+x));

const sums = [];
for(let i=0; i < N; i++) {
    let sum = 0;
    const weeks = [];
    let current = i;

    while(true) {
        if(current >= N) {
            break;
        }

        if(current + arr[current][0] <= N) {
            sum += arr[current][1];
            weeks.push(current);
        }
        current = arr[current][0] + current// T + current

    }
}

console.log(Math.max.apply(null, sums));

완전 틀리게 생각했다.
상담 기간이 끝난 후 있는 상담들 중 가장 효율적인 거를 구해야 하는데 그저 상담기간이 끝난 후 바로 오는 상담만 하는 것으로 로직을 짜서 틀렸다.

각 날짜에서 최고로 이득이 되게끔 한다. 그 최고의 이득들을 더하면서 날짜를 완성시킨다.
=> dp

두번째 시도

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const weekArr = input.map(x => x.trim().split(' ').map(x=>+x));

const sums = [];
const dp = new Array(N).fill(0);

for(let i=0; i < N; i++) {
    const [duration, money] = weekArr[i];
    if(duration + i > N) continue;
    dp[i] += money;
    for(let j = i + duration; j < N; j++) {
        dp[j] = Math.max(dp[j], dp[i]);
    }
}

console.log(Math.max.apply(null, dp)); 

참고 블로그
설명 참고 블로그
다른 풀이 블로그