백준 - 1912 연속합(Javascript)

1912 연속합

풀이과정

첫번째 접근 : 2차원 배열로 모든 경우의 수 때려넣기

다이나믹 프로그래밍이라 하면 주어진 문제 해결을 위해 여러 개의 하위 문제로 나누어 푸는 방법을 말한다. 부분 문제가 다른 문제들을 해결하는데 사용될 수 있어 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용하는 메모제이션 기법으로 속도를 향상시킨다.

근데 나는 다 구해버렸다…

dp[i][j]가 i번째 원소부터 j번째 원소까지의 합이 되도록 모든 값들을 구하고, 각 행에서 최대값을 maxArr에 넣어 그 중 최대값을 반환하도록 구현했다. 풀면서도 안되겠구나 생각은 했지만, 내가 원하는 방식으로 구현하는 연습을 하기 위해 그냥 끝까지 구현은 했다.
결과는 메모리 초과…

// 2차원 배열로 각 원소의 행 i, 열 j 값은 i부터 j까지의 합이 되도록 dp배열 구현
const dp = [...Array(N)].map(v => [...Array(N)].map(v => -1000 * N));
for (let i = 0; i < N; i++) {
  dp[i][i] = nums[i];
}
for (let i = 0; i < N; i++) {
  for (let j = i + 1; j < N; j++) {
    if (j - 1 >= 0) dp[i][j] = dp[i][j - 1] + dp[j][j];
  }
}

// 각 행별로 최대값을 배열에 담아 그 중 최대 값을 반환
const maxArr = [];
for (let i = 0; i < N; i++) {
  const max = Math.max(...dp[i]);
  maxArr.push(max);
}

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

두번째 접근

가장 간단한 부분해 찾기
그 부분해로부터 다른 문제의 해를 찾기

결국 다이나믹 프로그래밍으로 문제를 풀기 위해서는 이차원 배열이 아닌 일차원으로 만들어야 한다고 생각을 했고, 주어진 입력값 중 nums[N-1]이 dp[N-1]이 됨을 생각해 낼 수 있었다.
dp[N-1]이 결정되자, dp[N-2] = Math.max(nums[N-2], nums[N-2]+dp[N-1]의 방식으로 점화식을 세울수도 있었고 쉽게 문제를 해결할 수 있었다.

정답코드

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

const n = Number(input.shift());
const nums = input
  .shift()
  .split(' ')
  .map(v => Number(v));

const dp = [...Array(n)].map(v => 0);
dp[n - 1] = nums[n - 1];

for (let i = n - 2; i >= 0; i--) {
  dp[i] = Math.max(nums[i], nums[i] + dp[i + 1]);
}

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