백준, 14501 퇴사 자바스크립트

백준, 14501 퇴사 자바스크립트

📖 https://www.acmicpc.net/problem/14501

👨‍💻 문제 풀이

• ti + i <= j를 만족할때 dp[j] = dp[i]까지의 최댓값 + map[j] , dp[j] 중 최댓값
  

💻 제출한 코드

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

const N = +input.shift();
const map = [[0,0], ...input.map((row) => row.split(' ').map(Number))];

const dp = []

for(let i=0; i<=N; i++) {
    dp.push(map[i][1])
}

for(let i=0; i<=N; i++) {
    for(let j=1; j<=N; j++) {
        if(i + map[i][0] <= j) {
            // console.log(i, map[i][0], j);
            dp[j] = Math.max(dp[i] + map[j][1], dp[j])
            // console.log(dp);
        }
    }
    if(i + map[i][0] > N+1) dp[i] = -1;
}

console.log(Math.max(...dp));

이번 문제를 풀면서,

• 오랜만에 dp문제를 풀었고, 기본적인 문제가 아니고 조금 응용하는 문제를 풀었다.
• 로직은 틀리지 않게 짰는데 그걸 이중포문으로 구현하는데에 시간이 오래걸렸다.
• 또한, 비슷한 로직을 포문 한번으로 푸는 풀이가 많아서 풀이를 좀 기억해 놓아야 겠다는 생각이 들었다.