[백준 11053번 가장 긴 증가하는 부분 수열 - node.js] [알고리즘 기초 1/2]

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

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

예제 입출력

 

입력	출력
6 10 20 10 30 20 50	4

 

풀이[node.js]

 

 

728x90

 

dp를 어떻게 이용해야하는지 감도 안오던 문제였다.

먼저 각각의 inputs값에 0을 채워준다.

그리고 인덱스 0부터 5까지 돌면서 각각의 값이 앞의 숫자들보다 작은지 큰지 비교를 한다.

i가 20이고, j가 10인 경우에는 i값이 더 크다. 기본적으로 max값은 0이지만, i값이 더 크기 때문에, 더 작은 값인 j값의 dp값을 max에 넣어준다. 

이렇게 만약 앞의 값보다 해당 인덱스 값이 크다면 앞의 값의 dp값을 구해서 max값에 넣어준다.

해당 인덱스값보다 작은 값들의 dp를 다 돌면서, max값을 설정해주고, 해당 인덱스의 dp값은 max값에서 1을 더해준 값으로 지정해주면 된다.

여기서 주의할 점은, inputs의 i값이 j값보다 크다고 해서 무조건 max값을 해당 dp의 j값을 입력해주면 안된다.

그럴 경우에는 최대값이 max값으로 대입되는 것이 아니라, 가장 마지막에 들어온 dp[j]값이 max값으로 설정되기 때문이다.

30을 예로 들자면, 10, 20, 10이 모두 30보다 작다.

dp[j] > max로 설정해주지 않는다면, 가장 마지막 dp[j]값인 1이 max값이 되어 30의 dp값이 1+1인 2가 되버린다.

그렇기에, dp[j]가 max보다 큰지 확인하고, 더 큰 값이라면 그 값을 dp[j]로 설정해준다.

 

 

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = Number(inputs[0]);
var inputs = inputs[1].split(' ').map(v=>Number(v));
var dp = new Array(cases).fill(0);
for(var i=0; i<cases; i++){
    var max = 0;
    for(var j=0; j<i; j++){
        if(inputs[i] > inputs[j] && dp[j] > max){
            max = dp[j];
        }
    }
    dp[i] = max + 1;
}
console.log(Math.max(...dp));