[백준] 1912 - dp

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

let N = parseInt(input[0]);

//N만큼 배열에 담아주기
let dp = new Array(N).fill(0);

//N만큼 값 담아오기
let list = input[1].split(' ').map((item) => parseInt(item));

//dp[0]은 list[0]으로 초기화
dp[0] = list[0];

//dp[i]는 dp[i-1]과 list[i]를 비교해서 큰 값을 넣어준다.
for (let i = 1; i < N; i++) {
  dp[i] = Math.max(dp[i - 1] + list[i], list[i]);
}

//dp배열 중 가장 큰 값을 찾아서 출력
console.log(Math.max(...dp));

dp를 풀면서 점화식 짜는게 항상 너무 어려운 것 같다. 그래도 한 문제 씩 풀면서 점화식을 만들어가는 구조를 이해할 수 있는 것 같다. 위의 문제 같은 경우에는 첫 번째 요소를 넣어두고 두 번째 요소 부터 하나씩 비교해가면서 이전에 연속된 값의 합과 현재 요소 값을 비교했을 때 더 큰 값을 dp에 넣어주고 이전 값을 계속해서 들고와서 비교해주는 식으로 작성을 해주면 됐다.