BOJ 11055 가장 큰 증가하는 부분 수열 (JS)

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

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const n = Number(input.shift());
const arr = input[0].split(" ").map(Number);
const dp = [...arr];

// 5 4 3 2 10
for (let i = 0; i < arr.length - 1; i++) {
  for (let target = i + 1; target < arr.length; target++) {
    if (arr[i] < arr[target]) {
      dp[target] = (dp[i] + arr[target]);
    }
}
console.log(dp)
}

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

이렇게 푸니까 테스트 케이스는 통과하였는데 실패한다.. 왜 그럴까?

 

만약 배열이 [5,4,3,2,10]으로 구성되어 있을때

 

답은 [5, 10] = 15가 되어야 하는데, 초기에 15를 마지막 원소에 저장은 하지만 이후에 dp[target]에 기존 dp[target]값과 비교를 하지 않고 집어넣어 더 작은 수가 와도 집어넣는 것을 볼 수 있다.

 

따라서,

dp[target] =Math.max( (dp[i] + arr[target]), dp[target]);

다음과 같이 고쳐주면 된다.