[백준 2104] 부분배열 고르기 with Node.js

문제 링크

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

2104번: 부분배열 고르기

풀이

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split(/\s/);
const N = +input[0];
const A = input.slice(1).map(v => +v);
const sums = Array(N+1).fill(0);
A.forEach((v, i) => sums[i+1] = sums[i] + v);

const dnq = function (l, r) {
    if (l == r) return A[l]*A[l];

    const m = Math.floor((l+r)/2);
    const LEFT = dnq(l, m);
    const RIGHT = dnq(m+1, r);

    let tmpL = m;
    let tmpR = m+1;
    let low = Math.min(A[tmpL], A[tmpR]);
    let MID = (sums[tmpR+1]-sums[tmpL])*low;
    let tmp_score;

    while (tmpL > l || tmpR < r) {
        if (tmpL > l && (tmpR === r || A[tmpL-1] > A[tmpR+1])) {
            low = Math.min(low, A[--tmpL]);
            tmp_score = (sums[tmpR+1]-sums[tmpL])*low;
        } else {
            low = Math.min(low, A[++tmpR]);
            tmp_score = (sums[tmpR+1]-sums[tmpL])*low;
        }
        MID = Math.max(MID, tmp_score);
    }

    return Math.max(LEFT, RIGHT, MID);
};

console.log(dnq(0, N-1));

분할정복을 활용하여 먼저 전체 구간을 반으로 나눈다.

반으로 나눈 왼쪽 구간과 오른쪽 구간은 재귀호출을 통해 최댓값을 각각 LEFT와 RIGHT에 저장한다.

 

왼쪽 구간과 오른쪽 구간에 걸쳐 있는 경우를 생각해보자.

두 구간에 걸쳐 있는 최댓값을 찾으려면, 왼쪽 구간의 가장 마지막 요소와 오른쪽 구간의 첫 번째 요소 두 개를 포함하는 최댓값을 찾아야 한다.

문제 예시에 나와 있는 3 1 6 4 5 2를 입력했다면, 6과 4를 포함하는 최댓값을 찾아야 한다.

 

이제부터 왼쪽 또는 오른쪽으로 숫자를 더 늘려가며 더 큰 값이 나올 수 있는지 확인해야 한다.

이 때 왼쪽과 오른쪽 중 더 큰 것부터 포함시키며 점수를 확인한다.

6과 4의 양 옆에 1과 5가 있다.

이 중에 더 큰 5부터 먼저 포함시켜서 6 4 5로 점수를 계산한다.

그 다음에는 1과 2중에서 2를 포함시켜 6 4 5 2로 점수를 계산하고,

오른쪽 구간에 남은 수가 없기 때문에 이제부터는 왼쪽 구간 수를 하나씩 포함하며 점수를 계산한다.

(6 4 ▶ 6 4 5 ▶ 6 4 5 2 ▶1 6 4 5 2 ▶ 3 1 6 4 5 2)

 

이렇게 해서 구한 최댓값을 MID에 저장하고

최종적으로 LEFT, RIGHT, MID 중에 최댓값을 반환한다.

 

여기서 점수를 계산할 때, A[tmpL]부터 A[tmpR]까지의 합을 그 때 그 때 구하지 않고,

미리 sums 배열을 만들어서 누적합을 저장해놓았다.

처음에 이 sums 배열을 만들지 않고 점수를 계산하였더니 시간 초과로 통과하지 못하였다.