백준 11054: 가장 긴 바이토닉 부분 수열 - javascript(dp)

문제 출처 

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

 

정답 풀이 

 

• increaseDP 배열:
  • 앞에서부터 현재 원소까지의 가장 긴 증가 부분 수열의 길이를 저장합니다.
  • 각 원소에 대해, 이전 원소들과 비교하여 자신보다 작은 값을 만나면 그 길이에 1을 더해 더 긴 수열로 갱신합니다.
• decreaseDP 배열:
  • 뒤에서부터 현재 원소까지의 가장 긴 감소 부분 수열의 길이를 저장합니다.
  • 각 원소에 대해, 이후 원소들과 비교하여 자신보다 작은 값을 만나면 그 길이에 1을 더해 더 긴 수열로 갱신합니다.
• 결과 계산:
  • 각 인덱스에서 증가 부분과 감소 부분 수열을 더한 값을 구하고, 이 값 중 가장 큰 값을 선택합니다.
  • 증가 부분과 감소 부분에서 현재 원소가 두 번 더해지므로 마지막에 1을 빼줍니다.

 

 

각  증가하는 수의 길이 최솟값은 자기 자신 1이다. 

 

5는 1보다 크다. 

1의 dp 값에 +1 을 한다. 

 

 

 

2는 1보다만 크다. 

1의 dp 값 1에다가 +1을 한다. 

 

이런식으로 채워나가다보면, 아래 배열이 나온다. 

 

 

이제. 감소하는 수열 길이를 채워나가보자. 

뒤에서부터 채울 것이다. 

 

 

 

 

 

그럼, 각 수를 기준으로 중가하는 수열 길이와 감소하는 길이를 다 구했다. 

 

각 수를 더하고 자기를 포함한 하나의 수가 중복됐으니, -1을 하면된다. 

 

정답 코드 

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

const n = +input[0];
const nums = input[1].split(" ").map(Number);

const increaseDP = new Array(n).fill(1);
const decreaseDP = new Array(n).fill(1);

// 증가 DP 구하기
for (let i = 0; i < n; i++) {
  for (let j = 0; j < i; j++) {
    if (nums[i] > nums[j]) {
      increaseDP[i] = Math.max(increaseDP[i], increaseDP[j] + 1);
    }
  }
}

// 감소 DP 구하기
for (let i = n - 1; i >= 0; i--) {
  for (let j = i + 1; j < n; j++) {
    if (nums[i] > nums[j]) {
      decreaseDP[i] = Math.max(decreaseDP[i], decreaseDP[j] + 1);
    }
  }
}

// 최종 결과 계산
let maxLength = 0;
for (let i = 0; i < n; i++) {
  maxLength = Math.max(maxLength, increaseDP[i] + decreaseDP[i] - 1);
}

console.log(maxLength);

 

아래는, 똑같은 코드이지만 맨 앞쪽 increase_dp 배열의 0번째 idx는 그냥 1이니까 넘겼고, 

맨 뒤쪽 decrease_dp 배열의 마지막 idx는 그냥 1이니까 넘긴 코드다. 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const n = Number(input.shift()); 
input = input[0].split(' ').map(v => +v);  // input[0]을 split하여 숫자 배열로 변환

let increase_dp = new Array(n).fill(1);
let decrease_dp = new Array(n).fill(1);

// 증가하는 부분 수열 계산
for(let i = 1; i < n; i++){
    for(let j = 0; j < i; j++){
        if(input[j] < input[i]){
            increase_dp[i] = Math.max(increase_dp[j] + 1, increase_dp[i]);
        }
    }
}

// 감소하는 부분 수열 계산
for(let i = n - 2; i >= 0; i--){
    for(let j = i + 1; j < n; j++){
        if(input[j] < input[i]){
            decrease_dp[i] = Math.max(decrease_dp[j] + 1, decrease_dp[i]);
        }
    }
}

// 가장 긴 바이토닉 수열 길이 계산
let max = 1;
for(let i = 0; i < n; i++){
    max = Math.max(max, increase_dp[i] + decrease_dp[i] - 1);
}

console.log(max);