백준 11053: 가장 긴 증가하는 부분 수열 - javascript(dp)

문제 출처 

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

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

문제 풀이 힌트 

바로 이해가 가진 않을 것이다. 한줄한줄 읽어보면서 이해해보자. 

 

- dp 배열을 생성하고 해당 수를 포함시켰을 때 총 몇개의 수열을 포함시키는지 그 수를 dp 배열에 채워넣는다. 

- dp[0] = 1이다. 

- 반복문을 통해 각 A의 수를 만난다. 

ex0) 10은 dp의 값이 1이다. 즉 dp[0] = 1;

ex1) 20을 만났을 때 20이전의 모든 수를 돌아보자. 10이 있다. 20은 10보다 크고(조건 1), 그러니 dp[0] = 1 값에 +1 을 한다. 

ex2) 10을 만났을 때 10이전의 모든 수를 돌아보자. 10이 있다.. 10은 10보다 크지 않다, 10은 20보다 크지 않다. 그러니 dp[2] = 1이 된다. 

ex3) 30을 만났을 때 20이전의 모든 수를 돌아보자. 10이 있다. (dp[0] = 1) 20이 있다. (dp[1] = 2) 10 (dp[2] = 1)이 있다. 모든 세수가 조건1을 만족한다. dp[idx]가 가장 큰 값에 +1 을 한다. 즉, dp[3] = 3이 된다. 

ex4)20을 만났을 때 이전의 모든 수를 돌아보자. 그때 조건 1에 만족하는 경우는 idx가 0과 2인 경우다. dp[0] = 1 dp[2] = 1 모두 1이니, dp[4] = 1 +1 이 된다. 

ex5) 50을 만났을 때 이전의 모든 수를 돌아보자. 그때 조건1에 만족하는 경우는 모든 수다. 그 중, dp[idx] 값이 가장 큰 경우는 3이다. 즉, dp[5] = 3+1 이 된다. 

 

  A =  10, 20, 10, 30, 20, 50 

dp = [1]

dp = [1,  2]

dp = [1,  2,   1]

dp = [1,  2,   1,  3]

dp = [1,  2,   1,   3,   2]

dp = [1,  2,   1,   3,   2,   4]

문제 풀이 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const N = Number(input[0]); 
const A = input[1].split(' ').map(v => +v); 

const dp = new Array(N); //수열 A의 idx를 포함 시킬 때 횟수 저장 
dp[0] = 1; 

for(let i=1; i<N; i++){//dp[i]를 채울 것임 
    let max = 0; //max는 계속 초기화 
    for(let j=0; j<i; j++){//i이전의 모든 수 탐색하기 
        if(A[j] < A[i]){ //i의 수가 j수보다 클때 (조건1)
            max = Math.max(max, dp[j]); //이제껏 만났던 j의 dp[j]값 즉, max와 현재 만난 j의 dp[j]값중 더 큰것을 max에 할당
        }
    }
    dp[i] = max+1; 
}

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

Only 문제 풀이 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const N = Number(input[0]); 
const A = input[1].split(' ').map(v => +v); 

const dp = new Array(N); 
dp[0] = 1; 

for(let i=1; i<N; i++){
    let max = 0; 
    for(let j=0; j<i; j++){
        if(A[j] < A[i]){
            max = Math.max(max, dp[j]); 
        }
    }
    dp[i] = max+1; 
}

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