BOJ 25289 - 가장 긴 등차 부분 수열 (Javascript)

문제 링크

https://www.acmicpc.net/problem/25289

25289번: 가장 긴 등차 부분 수열

 

풀이

등차수열의 공차가 고정되었다고 생각하면 정말 간단한 dp 문제가 됩니다.

$d[\text{num}]$: 공차 $\text{diff}$에 대해, $\text{num}$이 끝 부분에 위치하는 등차수열의 최대 길이.

$d[\text{num}] = d[\text{num} - \text{diff}] + 1$

 

원소의 범위가 1 ~ 100이기 때문에 공차의 범위는 -99 ~ 99입니다. 각 공차마다 위 dp를 적용하면 복잡도 $O(200N)$으로 해결 가능합니다.

 

정답 코드

// @BOJ ------------------------------------------
const fs = require('fs');
const stdin = fs.readFileSync('/dev/stdin').toString().split('\n');
const input = (() => {
  let line = 0;
  const input = () => stdin[line++];
  input.num = () => input().split(' ').map(Number);
  input.rows = l => Array(l).fill().map(input);
  input.rows.num = l => Array(l).fill().map(input.num);
  return input;
})();

// Solution -----------------------------------
const range = (s, e) =>
  Array(e - s)
    .fill()
    .map((_, i) => i + s);

const DIFF_MAX = 100;
const solve = seq =>
  Math.max(
    ...range(0, DIFF_MAX).map(diff =>
      Math.max(
        ...seq.reduce((d, v) => {
          d[v] = v > diff ? d[v - diff] + 1 : 1;
          return d;
        }, Array(DIFF_MAX + 1).fill(0)),
      ),
    ),
  );

const solution = function () {
  const n = +input();
  const seq = input.num();

  console.log(Math.max(solve(seq), solve(seq.reverse())));
};

solution();