BOJ_11055 가장 큰 증가 부분 수열

• TOC {:toc}

이 글은 백준 온라인 저지의 11055번 문제를 자바스크립트(JavaScript)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2023.02.24

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, line] = input;
const seq = line.split(" ").map((n) => parseInt(n));

function main() {
    const maxSum = Array(N).fill(0);
    for (i = 0; i < N; i += 1) {
        let max = 0;
        for (j = 0; j < i; j += 1) {
            if (seq[i] > seq[j]) {
                max = Math.max(max, maxSum[j]);
            }
        }
        maxSum[i] = seq[i] + max;
    }
    return Math.max(...maxSum);
}

console.log(main());

아이디어 & 풀이

각 수열값에 대해서 해당 값까지의 수열로 만들 수 있는 부분 수열의 합중 최댓값(maxSum)을 순차적으로 구한다.

• 각 수열값에 대해서 새로운 값을 구할 때 이전에 구한 값을 사용한다.
  • 현재값보다 이전(인덱스가 낮은)값을 순회하면서 이전값이 현재값보다 작으면 현재값을 그 수열에 이을 수 있다.
  • 그러므로 현재값들보다 작은값의 maxSum 값중 최댓값에 현재 수열의 값을 더한 값이 현재값의 maxSum 값이다.

예제에서 maxSum이 업데이트 되는 과정을 보면.

우선 1과 100은 선택지가 없으므로 설명없이 채운다.

2(i: 2)의 maxSum값을 구할 때

• [i: 0] 1은 2보다 작으므로 2가 이어질 수 있다.
• [i: 1] 100은 2보다 크므로 2가 이어질 수 없다.
• 유일한 값인 1에 2를 더한 값인 3이 2의 maxSum 값이다.

다음으로 50(i: 3)의 maxSum값을 구할 때

• [i: 0] 1은 50보다 작으므로 50이 이어질 수 있다.
• [i: 1] 100은 50보다 크므로 50이 이어질 수 없다.
• [i: 2] 3은 50보다 크므로 50이 이어질 수 없다.
• 50을 이을 수 있는 1과 3중 최댓값인 3에 50를 더한 값인 53이 50의 maxSum 값이다.

위와 같은 과정을 반복하면서 8까지 maxSum값을 구한 뒤 그 중 최댓값을 구하면 된다.

피드백

• if (seq[i] > seq[j]) 안에서 max 값을 구하는 게 아니라 maxSum값을 바로바로 업데이트할 수도 있다.
  • 이 경우 max 변수를 사용하지 않아도 되므로 코드가 훨씬 간결해진다.