백준 11722번: 가장 긴 감소하는 부분 수열 - javascript

백준 11722번: 가장 긴 감소하는 부분 수열

문제 설명

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

입력

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

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

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

접근

이 문제는 11053번 가장 긴 증가하는 부분 수열의 반대버전이다. 11053번은 증가했지만 이 문제는 감소하기만 하면된다.

풀이는 다음과 같다.
이번에도 역시 맨 앞에 최대 범위값보다 1 더 큰 1001을 추가해 놓는다.

원본 배열	1001	10	30	10	20	20	10
dp	0	1	-	-	-	-	-

10보다 큰 수는 1001밖에 없으므로 10에서의 최대 길이는 1

원본 배열	1001	10	30	10	20	20	10
dp	0	1	1	-	-	-	-

30보다 큰 수 중 1001이 최대 길이를 가지고 있으므로 1

원본 배열	1001	10	30	10	20	20	10
dp	0	1	1	2	-	-	-

10보다 큰 수는 30과 1001인데 그 중 30이 1을 갖고있어서 최대값이므로 10의 값은 1+1

원본 배열	1001	10	30	10	20	20	10
dp	0	1	1	2	2	-	-

20보다 큰 수는 30과 1001인데 그 중 30이 1을 갖고있어서 최대값이므로 20의 값은 1+1

원본 배열	1001	10	30	10	20	20	10
dp	0	1	1	2	2	2	-

20보다 큰 수는 30과 1001인데 그 중 30이 1을 갖고있어서 최대값이므로 20의 값은 1+1

원본 배열	1001	10	30	10	20	20	10
dp	0	1	1	2	2	2	3

10보다 큰 수는 30과 20, 그리고 1001인데 그 중 20이 2를 갖고있어서 최대값이므로 10의 값은 2+1

이렇게 나온 dp배열의 max값을 반환하면 정답 3이 나온다.

정답 코드

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 = '1001 '+ input[1]
  arr = arr.split(' ')
  answer = max_decrease_array(n, arr);  
  console.log(answer)
  process.exit();
});

function max_decrease_array(n, arr){
  let dp = new Array(parseInt(n)+1).fill(0)
  for(let i=1;i<=n;i++){
    let max = 0;
    for(let j=0;j<i;j++){
      if(arr[j]*1 > arr[i]*1){
        max = Math.max(dp[j],max)
      }
    }
    dp[i] = max+1;
  }
  return Math.max(...dp)
}