[node.js,백준]11722 - 가장 긴 감소하는 부분수열

목차

 

 

 문제

링크

https://www.acmicpc.net/problem/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의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

 

주저리

가장 긴 감소하는 부분수열의 길이를 구하는 문제

일단 자기자신이 포함되므로 길이는 1로 시작

그리고 자기보다 앞의 수들을 비교하여

자기보다 앞의 수가 자신보다 작을때 배열을 추가하여

그중 제일 많은 갯수를찾은후 자신을 더해서 반환해준다.

그렇게해서 마지막 에서 제일 많은 배열의 갯수를 찾아 출력해주면 끝.

 

풀이

 입력 처리

• 입력은 두 줄의 문자열로 제공됩니다. 첫 번째 줄은 수열의 길이 N, 두 번째 줄은 수열의 요소입니다. 이 요소들은 공백으로 구분되어 있으며, 자바스크립트의 map 함수를 사용하여 정수 배열로 변환됩니다.

 초기화

• 수열의 각 원소에 대해, arrs 배열은 해당 원소를 마지막으로 하는 LDS의 최대 길이를 저장합니다. 초기 길이는 모두 1로 설정되며, 이는 수열의 각 원소가 최소한 자기 자신만을 포함하는 부분 수열을 형성할 수 있음을 의미합니다.

 동적 프로그래밍 로직 실행

• 메인 알고리즘은 각 원소를 차례대로 확인하면서, 이전 원소들과 비교하여 감소하는 부분 수열을 찾습니다. 현재 원소보다 큰 이전 원소를 찾으면, 해당 원소의 LDS 길이에 1을 더한 값을 현재 원소의 LDS 길이로 갱신합니다. 이 과정은 모든 원소에 대해 반복됩니다.

 결과 출력

• 계산된 arrs 배열에서 가장 큰 값이 가장 긴 감소하는 부분 수열의 길이가 됩니다. 이 값은 최종적으로 콘솔에 출력됩니다.

 코드

// 가장 긴 감소하는 부분 수열
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString();

let real = input.trim().split("\n");
let arrs = [];

function testF(N, rest) {
    // for (let i = 0; i < 1; i++) arrs[0][i] = 1;

    for (let i = 0; i < N; i++) {
        // let reArr = [];
        if (i === 0) {
            arrs[i] = 1
        }
        else {
            arrs[i] = 1;
            let sliced = rest.slice(0, i);
            let filtered = [];
            for (let j = 0; j < sliced.length; j++) {
                let r = sliced[j];
                // console.log(rest[i], r, rest.slice(0, i));
                if (rest[i] < r) {
                    filtered.push(arrs[j]);
                }
            }
            if (filtered.length > 0) {
                arrs[i] = Math.max(...filtered) + 1
            }

        }
        // arrs.push(reArr);
    }
}

function solution(real) {
    let [T, sec] = real;

    let rest = sec.split(" ").map(Number);
    testF(Number(T), rest)

    // console.log(arrs)
    console.log(Math.max(...arrs))
}
solution(real);