[백준][node.js] 11053.가장 긴 증가하는 부분 수열

문제 유형

동적 계획법

 

문제

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

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

 

입력

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

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

 

출력

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

 

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

 

 

풀이

기준 인덱스를 설정하고 for문을 도는 방식이다. 

기준 인덱스인 i를 두고 기준 인덱스보다 이전 인덱스들인 j들을 for문으로 순회해서 i보다 작은 요소들인지 확인하면 된다. 

기준 인덱스 i가 이전 인덱스인 j보다 작으면 기준 인덱스의 dp값을 구한다. 

 

dp에 j를 돌때마다 max값을 설정해 넣어주면된다. 

 

 

예시) 10 20 10 30 20 50

dp	i	j	max
[]	0	0	1
[1]	1	0	1
		1	1
[1,2]	2	0	0
		1	0
		2	0
[1,2,1]	3	0	1
		1	2
		2	2
[1,2,1,3]

와 같은 과정으로 dp배열을 구하는 과정이 진행된다.

이와 같은 계산을 진행하면 마지막으로 dp배열은 [1,2,1,3,2,4] 가 나오게 되어 최댓값인 4.

즉, 증가하는 숫자의 진행은 4개 있다라는 뜻이 된다. 

 

 

코드

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

const num = +input[0];
const arr = input[1].split(" ").map((v) => +v);
const dp = [];

for (let i = 0; i < num; i++) {
  let max = 0;

  for (let j = 0; j < i; j++) {
    if (arr[i] > arr[j] && dp[j] > max) {
      max = dp[j];
    }
  }
  dp[i] = max + 1; // 자기 자신도 더하기
}

console.log(Math.max(...dp));