[백준] 11055번: 가장 큰 증가 부분 수열 (JavaScript, NodeJS)

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력 1 복사

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1 복사

113

정답 풀이

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; // 리눅스로 테스트할 땐 따로 설정해주어야 합니다.
const [n, sequence] = require("fs")
  .readFileSync(path)
  .toString()
  .trim()
  .split("\n");
const seq = sequence.split(" ").map(Number);

function solution(n, seq) {
  const memo = new Array(n).fill(0);

  for (let i = 0; i < n; i += 1) {
    let max = 0;
    let maxIndex = -1;

    for (let j = 0; j < i; j += 1) {
      if (seq[i] > seq[j] && memo[j] > max) {
        max = memo[j];
        maxIndex = j;
      }
    }

    memo[i] = maxIndex === -1 ? seq[i] : seq[i] + memo[maxIndex];
  }

  return Math.max(...memo);
}

const answer = solution(n, seq);
console.log(answer);

⭐ 문제 핵심 아이디어 ⭐
1. DP

아직 DP가 익숙하지 않아서 도저히 감이 잡히지 않았다..

왜케 어려운 것인가 디피는!!!!!!!

 

블로그들을 참고하다가

 

https://leylaoriduck.tistory.com/527

 

해당 블로그에서 아이디어를 얻고 (사실 그림을 보고도 코드로 어떻게 짜야할 지 잘 몰랐다.)

하나하나 분석을 해가면서 천천히 풀었다.