[boj] 13398. 연속합 2 (node.js)

문제

[boj] 13398. 연속합 2 (node.js)

• 최대 연속합을 구하는 문제
• 최소한 하나의 숫자가 연속되어야 하며, 하나의 숫자를 제거(무시)할 수 있다.

풀이

• 배열을 순회하며 N번째 원소까지의 최대 연속합을 구한다.
• 제거 조건: 연속합은 양수를 더하는 경우 항상 증가하므로, 해당 인덱스에서의 값이 음수일 때만 제거를 고려한다.
• dp[N][0]: 하나의 숫자를 제거하지 않는 경우 해당 인덱스까지의 최댓값
• dp[N][1]: 하나의 숫자를 제거한 경우 해당 인덱스까지의 최댓값
  • 기존에 제거된 경우와 이번에 제거하는 경우 중 더 큰 값을 저장
  • 이번에 제거하는 경우는 현재 값을 무시하는 것과 같으므로 dp[N-1][0]을 참조한다.

for (let i = 1; i < N; i++) {
  dp[i] = [];
  dp[i][0] = Math.max(dp[i - 1][0] + arr[i], arr[i]);
  dp[i][1] = dp[i - 1][1] + arr[i];
  if (arr[i] < 0) dp[i][1] = Math.max(dp[i - 1][0], dp[i][1]);
  result = Math.max(...dp[i], result);
}

생각

• 세 번 틀리며 느낀 주의할 점
  • 초기값: 결과값을 저장하는 변수의 초기값에 유의해야 한다. 이 문제는 '연속합'을 구해야 하므로 무조건 최소값(-1000)으로 설정하면 틀린다. 내가 풀이한 방법에서는 배열을 순회하며 값이 계속 갱신되므로, 배열의 첫 번째 원소로 초기값을 설정했다.
    • 그 외에도 dp 배열의 초기값, Math.max 갱신시의 초기값을 모두 한번씩 더 시뮬레이션해보며 확인해보는 것이 중요하다!

전체 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const N = input();
  const arr = input().split(" ").map(Number);
  const dp = [[arr[0], arr[0]]];

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

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});