[백준] 11053번: 가장 긴 증가하는 부분 (JavaScript, NodeJS)

문제

수열 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

정답 풀이

const fs = require('fs');
// 백준 제출 할 때 주석 제거
// const readFileSyncAddress = '/dev/stdin';
// VSC 테스트 할 때 주석 제거
const readFileSyncAddress = 'input.txt';

let input = fs.readFileSync(readFileSyncAddress).toString().trim().split('\n');

// 인풋 처리
[n, arr] = input;
n = Number(n);
arr = arr.split(' ').map(i => Number(i));

solution(n ,arr);

// 문제 풀이
function solution(n, arr) {
    if (n === 0) console.log(0);
    else if (n === 1) console.log(1); 
    else {
        let dp = new Array(n).fill(1);
        for (let i = 1; i < n; i++) {
            const current = arr[i];
            const values = [1];
            for (let j = 0; j < i; j++) {
                const before = arr[j];
                if (current > before) values.push(dp[j] + 1);
            }
            dp[i] = Math.max(...values);
        }
        console.log(Math.max(...dp));
    }
}