[node.js,백준]11055 - 가장 큰 증가하는 부분 수열

목차

 

 

 문제

링크

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

문제

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

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

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

 

출력

첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

 

주저리

증가하는 부분수열중에서 그 값들을 비교해 가장 큰 출력값에다가 자신의 숫자를 더해서 누적하여 답을 구했다.

만약 증가하는 수열이 없다면 arrs[i]엔 자신을 넣는다.

 

풀이

 입력 처리

• 수열의 길이와 수열 자체를 문자열에서 추출합니다.
• 추출된 문자열을 숫자 배열로 변환하여 수열 데이터를 준비합니다.

 testF 함수 실행

• 초기화
  • 함수 내에서 arrs라는 배열을 사용하여 각 원소를 마지막으로 하는 최대 부분 수열의 합을 저장합니다. 초기에는 arrs 배열의 각 요소를 rest의 해당 요소로 설정하여 시작합니다.
• 핵심 로직
  • 함수의 메인 로직은 두 개의 중첩된 반복문을 사용하여 수행됩니다. 바깥쪽 반복문은 수열의 각 원소를 순회하고, 안쪽 반복문은 현재 원소의 인덱스보다 앞에 있는 모든 원소를 검사합니다.
  • 바깥쪽 루프 (i): 이 루프는 수열의 각 원소를 차례로 고려합니다. i는 현재 원소의 인덱스입니다.
  • 안쪽 루프 (j): j 루프는 i보다 작은 모든 인덱스를 순회합니다. 이는 i번째 원소 앞에 있는 모든 원소들을 확인하며, 현재 원소보다 작은 값을 찾아내는 역할을 합니다.
  • 필터링 및 최대값 업데이트: filtered 배열은 현재 원소보다 작은 이전 원소들의 최대 부분 수열 합을 저장합니다. Math.max(...filtered)를 사용하여 이전 원소들 중 최대 합을 찾고, 현재 원소의 값(rest[i])을 더하여 arrs[i]를 업데이트합니다.

 배열 'arrs' 초기화

• 각 원소가 마지막 원소인 부분 수열의 최대 합을 저장할 배열을 초기화합니다.
• 초기에 모든 원소는 자신의 값으로 설정됩니다.

 최대 합 계산

• 이중 루프를 통해 각 원소에 대해 이전 모든 원소를 검토합니다.
• 현재 원소보다 작은 모든 이전 원소의 최대 합을 찾아 현재 원소와 더합니다.

 최대 합의 업데이트

• filtered 배열에 원소가 있으면, 해당 원소들 중 최대값에 현재 원소 값을 더하여 최대 합을 업데이트합니다.

 최종 결과 출력

• 계산을 마친 후, 최대 부분 수열 합을 출력합니다.

 코드

// 가장 긴 증가하는 부분 수열
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] = rest[0]
        }
        else {
            arrs[i] = rest[i];
            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) + rest[i]
            }

        }
        // 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);