[BOJ] 2313 - 보석 구매하기

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

BOJ - 보석 구매하기

문제 유형: 다이나믹 프로그래밍, 구간 합

문제 난이도: Gold V

시간 제한: 2초

메모리 제한: 128MB

 

문제

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

보석들은 총 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개의 수들을 하나의 수열로 생각하여, 사전식으로 가장 앞에 오는 경우를 출력한다.

 

풀이

각 n개의 케이스들에 대해서,

dp[i] = {구간합의 시작 인덱스, 누적 구간합}으로 했다.

dp[1]을 초기화해준 뒤, 2부터 l까지 순차적으로 다음과 같이 처리한다:

• 만약 이전 구간합에 이어붙인게 더 크다면, 이전 구간합을 기반으로 dp[j]를 채운다.
• 만약 이번에 새로 시작하는 구간합이 더 크다면, dp[j]를 새로 시작한다.

그 뒤,

만약 누적 구간합기존 최대합보다 더 크거나,

누적 구간합은 같고 l, r범위가 더 좁거나,

누적 구간합, l, r범위의 차가 같은데 구간합의 시작이 더 앞

이라면 최대합을 업데이트하고, 답이 될 구간 L, R도 새로 업데이트한다.

 

총 누적 최대합과 배열별 최종구간들을 출력해준다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pill pair<int, long long>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    ll ans = 0;
    vector<pii> ranges(n);

    for (int i = 0; i < n; i++) {
        int l;
        cin >> l;
        vector<int> arr(l + 1);
        vector<pill> dp(l + 1);

        for (int j = 1; j <= l; ++j) {
            cin >> arr[j];
        }

        ll maxSum = arr[1];
        dp[1] = {1, arr[1]};
        int L = 1, R = 1;
        for (int right = 2; right <= l; right++) {
            ll extended = dp[right - 1].second + arr[right];
            ll init = arr[right];

            if (extended > init) {
                dp[right] = {dp[right - 1].first, extended};
            } else if (extended <= init) {
                dp[right] = {right, init};
            }

            if (dp[right].second > maxSum ||
                (dp[right].second == maxSum &&
                 right - dp[right].first < R - L) ||
                (dp[right].second) == maxSum &&
                    right - dp[right].first == R - L && dp[right].first < L) {
                maxSum = dp[right].second;
                R = right;
                L = dp[right].first;
            }
        }

        ans += maxSum;
        ranges[i] = {L, R};
    }

    cout << ans << "\n";
    for (const auto &q : ranges) {
        cout << q.first << " " << q.second << "\n";
    }

    return 0;
}