Skip to content
On this page

백준 11055 JavaScript

수정하기
문서 생성 2022-02-05 10:40:24 최근 수정 2022-02-05 10:41:30
On this page

문제

백준 11055

풀이

백준 11053과 유사하다. 해당 문제가 길이를 구하는 것이었다면 이 문제는 값만 더해주면 된다.

예시로 나온 수열은 다음과 같다.

1 100 2 50 60 3 5 6 7 8
  1. 처음 값 1은 비교대상이 없으니 그대로 넣어두고
  2. 100까지 증가하는 수열의 합은 100 전에 있는 1과의 합 101이다.
  3. 2까지 증가하는 수열의 합은 1과의 합 3이다.
  4. 50까지 증가하는 수열의 합은 1+2+50 .... 위와 같은 식으로 배열을 순회하며 각 인덱스까지의 증가하는 수열의 합을 DP라는 별도의 배열에 넣어준다.
    그 후에 배열에 들어가 있는 수열의 합 값 중 최댓값을 구하면 된다.
const readFileSyncPath = require('path').basename(__filename).replace(/js$/, 'txt');
// const readFileSyncPath = '/dev/stdin';
const input = require('fs').readFileSync(readFileSyncPath).toString().trim().split("\n");
const N = Number(input[0]);
const A = input[1].split(" ").map(v => Number(v));
const DP = new Array(N).fill(0);
DP[0] = A[0];
// 수열의 각 숫자를 순회
for (let i = 1; i < N; i++) {
// 자신보다 앞에 있는 숫자 중,
for (let j = 0; j < i; j++) {
// 자신보다 작은 수가 있다면
if (A[i] > A[j]) {
DP[i] = Math.max(DP[i], DP[j]);
}
}
// 자신과 더하기
// 그럼 배열의 각 값은 각 인덱스까지 증가하는 수열의 합이 된다.
DP[i] += A[i];
}
// 증가하는 부분 수열의 최댓값
console.log(Math.max(...DP));