백준_보석 구매하기_2313

보석 구매하기

문제

보석 가게에 여러 가지의 보석이 진열되어 있다. 각각의 보석은 정수로 표현되는 가치가 있다. 때로는 저주받은 보석이 있기 때문에 가치가 음수가 될 수도 있다.

보석들은 총 n개의 줄에 나열되어 있다. 이제 당신은 각각의 줄에서 몇 개의 보석을 구매하려 한다. 이때, 각 줄에서 보석을 구매할 때 연속적인 보석들을 구매해야 한다. 즉, 어느 한 줄에서 1, 2번 보석을 구매할 수도 있고, 2, 3번 보석을 구매할 수도 있지만, 1, 3번 보석을 구매할 수는 없다.

구매하는 보석의 가치의 총 합이 최대가 되도록 보석을 구매하는 방법을 찾아내는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 2×n개의 줄에는 n개의 줄에 나열된 보석들에 대한 정보가 주어진다. 먼저 각 줄에 나열된 보석의 개수 L(1 ≤ L ≤ 1,000)이 주어지고, 그 다음 줄에 L개의 정수들이 주어진다. 각 정수는 각 보석의 가치를 나타낸다. 보석의 가치는 절댓값이 10,000보다 작거나 같은 정수이다.

출력

첫째 줄에 보석의 가치의 총 합의 최댓값을 출력한다. 다음 n개의 줄에는, 줄에서 몇 번째 보석부터 몇 번째 보석까지를 구매했는지를 출력한다.

만약 최대가 되는 경우가 여럿이면, 구매한 보석들의 총 개수가 최소가 되는 방법을 출력한다. 이와 같은 경우도 여럿이라면, 출력한 n×2개의 수들을 하나의 수열로 생각하여, 사전식으로 가장 앞에 오는 경우를 출력한다.

예제 입력 1

2
5
30 70 -10 10 0
9
90 80 70 60 0 -60 0 60 -60

예제 출력 1

400
1 2
1 4

풀이 및 해설

출력값: 구매하는 보석의 가치의 총 합이 최대가 되도록 구매하는 방법

• 최대가 되는 경우가 여러개인 경우, 구매한 보석의 총 개수가 최소가 되는 방법 출력

Code

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

const n = +input[0]; // 보석이 나열되어있는 줄 개수

let resultValue = 0;
const buyArea = [];
for (let i = 1; i <= 2 * n; i += 2) {
    const L = +input[i]; // 보석의 개수
    const jewels = input[i + 1].split(' ').map(Number); // 보석 가치

    let maxValue = 0;
    let buyStart = 0;
    let buyEnd = 0;
    for (let start = 0; start < L; start++) {
        let acc = 0;
        for (let end = start; end < L; end++) {
            acc += jewels[end];
            // 더 큰 보석 가치를 얻을 수 있을 때
            if (acc > maxValue) {
                maxValue = Math.max(maxValue, acc);
                buyStart = start;
                buyEnd = end;
            }
            // 가치가 동일할 때 보석 개수가 더 작은거 선택
            else if (acc === maxValue) {
                if (buyEnd - buyStart > end - start) {
                    buyStart = start;
                    buyEnd = end;
                }
            }
        }
    }

    resultValue += maxValue;
    buyArea.push([buyStart + 1, buyEnd + 1]);
}

console.log(resultValue);
buyArea.forEach((buy) => console.log(buy.join(' ')));