[JS] 백준 11054번 : 가자 긴 바이토닉 부분 수열 - DP(다이나믹 프로그래밍)

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

11054번: 가장 긴 바이토닉 부분 수열

 

 

풀이방법

1. N크기의 배열에 현재 숫자가 뒤에서 가장 큰 숫자일 때의 가장 긴 바이토닉 부분 수열 중 갯수가 가장 큰 값을 넣는다

2. N크기의 배열에 현재 숫자가 앞에서 가장 큰 숫자일 때의 가장 긴 바이토닉 부분 수열 중 갯수가 가장 큰 값을 넣는다.

3. 두 배열을 구했으면 두 배열의 값들을 인덱스에 대응되는 값끼리 더하고 -1을 한다(자신 숫자가 겹치므로 -1로 제외)

4. 두 배열을 더하는 것은 가운데 숫자가 가장 큰 숫자일 때의 가장 긴 바이토닉 부분 수열 중 갯수가 가장 큰 값을 구하는 것임

6. 아래와 같이 두 배열을 만들면 된다.

 

 

내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let N = Number(input.shift());
let arr = input.shift().split(" ").map(Number);
let dp1 = Array.from({ length: N }, () => 1);
let dp2 = Array.from({ length: N }, () => 1);

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

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

console.log(Math.max(...dp1.map((v, i) => v + dp2[i] - 1)));

 

 

💢어려웠던점

1. 예상외로 문제를 도식화해내는 것은 빠르게 해냈다. 하지만 그 풀이를 할 때 빠르게 하지 못했다.

-DP문제여도 이중 for문을 써도 된다.-> 이중 for문을 쓰면 느리지 않을까에 고민함

2. 현재수가 앞이나 뒤에서 가장 큰 값일 경우의 부분 수열 길이를 넣을 때 불필요한 탐색은 하지 않는지에 대해 생각하다가 시간을 허비했다.

 -DP니까 이전의 숫자 한개만으로 어떻게 되지않을까 했지만 현재 숫자의 뒤나 앞에 있는 모든 숫자를 탐색하는 것은 필수였다.