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

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

문제 설명

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < … Sk-1 < Sk > Sk+1 > … SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

접근

이 문제는 11053번 가장 긴 증가하는 부분 수열의 양면 버전이다. 11053번에 비해 이번 문제는 최대로 증가하면서 최대로 감소하는 긴 부분 수열을 구해야한다.

그렇다면 최대로 증가하는 부분 수열과 최대로 감소하는 부분 수열간의 최대 교차부분을 값으로 산출하면 되는 것이다.

증가와 감소 두개의 수치를 측정하기 위해 dp배열을 2중으로 생성한다.

원본 배열	0	1	5	2	1	4	3	4	5	2	1	0
dp[0]	0	1	-	-	-	-	-	-	-	-	-	-
dp[1]	-	-	-	-	-	-	-	-	-	-	1	0

i = 0일 때, dp[0]은 앞에서 부터, 동시에 dp[1]은 n-i 부터 내려간다.

원본 배열	0	1	5	2	1	4	3	4	5	2	1	0
dp[0]	0	1	2	-	-	-	-	-	-	-	-	-
dp[1]	-	-	-	-	-	-	-	-	-	2	1	0

원본 배열	0	1	5	2	1	4	3	4	5	2	1	0
dp[0]	0	1	2	2	-	-	-	-	-	-	-	-
dp[1]	-	-	-	-	-	-	-	-	3	2	1	0

원본 배열	0	1	5	2	1	4	3	4	5	2	1	0
dp[0]	0	1	2	2	1	-	-	-	-	-	-	-
dp[1]	-	-	-	-	-	-	-	3	3	2	1	0

원본 배열	0	1	5	2	1	4	3	4	5	2	1	0
dp[0]	0	1	2	2	1	3	-	-	-	-	-	-
dp[1]	-	-	-	-	-	-	3	3	3	2	1	0

이렇게 진행하다 보면 최종적으로 아래와 같은 표가 나오게 된다.

원본 배열	0	1	5	2	1	4	3	4	5	2	1	0
dp[0]	0	1	2	2	1	3	3	4	5	2	1	-
dp[1]	-	1	5	2	1	4	3	3	3	2	1	0

이렇게 나온 dp 배열에 관하여 각 dp[0][i] + dp[1][i] 값끼리의 max값을 구하면 5+3으로 8이 나오게 된다.
이 8이라는 숫자는 앞에서부터 5까지, 뒤에서부터 5까지의 각각의 최대 부분 증가 수열의 길이이므로 중복되는 5에 관해 1을 빼주면 8-1로 정답 7이 나오게 된다.

ps
이번 문제를 풀면서 처음에 dp 배열을 초기화 해주기 위해서

let dp = new Array(parseInt(n)+2).fill([0,0])

의 형식을 썼었는데 정답이 무조건 n으로 나왔었다.
왜 그런가 생각해보니 ‘초기화’ 해줄 때 fill에 [0, 0]의 객체를 넣어줘버렸던 것이다!..
데이터 타입과 변수에서도 공부했었는데, 자바스크립트에서 객체는 참조에 의한 전달 방식을 가진다.
그러니 당연하게도 dp[0]의 0과 dp[n]의 0은 메모리상에서 같은 주소를 참조하니, i가 0부터 n까지 향하게 되면 전부 같은 dp값을 공유하게되서 n을 결과로 반환 할 수 밖에 없었던 것이다… :joy:
따라서 그냥 평범하게 반복문을 돌려가며 dp에 [0, 0]을 push해주는 방법을 사용하는 것으로 해결했다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let answer = '';
  let n = input[0];
  let arr = '0 '+ input[1] +' 0'
  arr = arr.split(' ')
  answer = bytonic_array(n,arr)
  console.log(answer)
  process.exit();
});

function bytonic_array(n,arr){
  n = parseInt(n)
  let dp = [];
  let result = [];
  for(let i = 0; i<n+2;i++){
    dp.push([0,0])
  }
  //new Array(parseInt(n)+2).fill([0,0])
  for(let i=1;i<=n;i++){
    let max = 0;
    let max_alt = 0;    
    for(let j=0;j<i;j++){
      if(arr[j]*1 < arr[i]*1){        
        max = Math.max(dp[j][0], max);
      }      
      if(arr[n*1+1-j]*1 < arr[n*1+1-i]*1){
        max_alt = Math.max(dp[n*1+1-j][1], max_alt);
      }
    }
    dp[i][0] = max+1;    
    dp[n*1+1-i][1] = max_alt+1;
  }
  dp.reduce((acc,cur)=>{
    result.push(cur[0]+cur[1])
  },0)
  return Math.max(...result)-1;
}