[BOJ][C++] 백준 2313번: 보석 구매하기

https://www.acmicpc.net/problem/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개의 수들을 하나의 수열로 생각하여, 사전식으로 가장 앞에 오는 경우를 출력한다.

 

풀이

입력 조건을 보면 보석 가치의 총 합은

최대 n*L*(보석의 가치 최댓값) = 1000*1000*10000 = 10,000,000,000 = 100억

23억을 한참 넘기므로 int가 아닌 long long으로 해야한다

 

보석 각 줄마다 dp 연산은 독립적으로 진행하지만 

출력 첫 줄에 최종으로 나온 값을 보여줘야하기 때문에

입력을 전부 다 받아서 저장해놓고 시작해야한다. (필자는 v라는 벡터를 사용했다)

 

dp[i] : 보석갯수, i번째까지의 최대합

        // dp
        vector<ci>dp(length); // dp[i] : 보석갯수, i번째까지의 최대합
        dp[0] = {1, v[i][0]};
        for(int j=1; j<length; j++) {
            ci before = dp[j-1];
            if(before.second<=0) {
                dp[j] = {1, v[i][j]};
            } else {
                dp[j] = {before.first+1, before.second+v[i][j]};
            }
        }

 

 

비교 조건이 까다롭다.

1. 보석의 가치의 합이 최대가 되어야함

2. 가치의 합이 같다면 -> 보석의 갯수가 적어야함

3. 가치도 같고 갯수도 같다면 -> 그나마 앞쪽인거

// 최대가 되는 첫번째 위치 구하기
        int index = 0;
        int cnt = dp[index].first;
        int max_value = dp[index].second;
        for(int j=1; j<length; j++) {
            if(dp[j].second>=max_value) {
                if(dp[j].second==max_value && dp[j].first>=cnt) {
                    continue;
                }
                index = j;
                max_value = dp[j].second;
                cnt = dp[j].first;
            }
        }

 

게시판에 친절한 반례 모음이 있다.

아래 글에 나와있는 반례를 다 성공하면 거의 성공이다

https://www.acmicpc.net/board/view/139927

 

 

코드

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> ci;

int main() {
	// 입력
	int n;
	cin >> n;
	vector<vector<int>>v(n);
    for(int i=0; i<n; i++) {
        int tmp;
        cin >> tmp;
        v[i] = vector<int>(tmp);
        for(int j=0; j<tmp; j++) {
            cin >> v[i][j];
        }
    }
    
    // 풀이
    ll sum = 0;
    vector<ci> ans(n);
    for(int i=0; i<n; i++) {
        int length = v[i].size();
        
        // dp
        vector<ci>dp(length); // dp[i] : 보석갯수, i번째까지의 최대합
        dp[0] = {1, v[i][0]};
        for(int j=1; j<length; j++) {
            ci before = dp[j-1];
            if(before.second<=0) {
                dp[j] = {1, v[i][j]};
            } else {
                dp[j] = {before.first+1, before.second+v[i][j]};
            }
        }
        
        // 최대가 되는 첫번째 위치 구하기
        int index = 0;
        int cnt = dp[index].first;
        int max_value = dp[index].second;
        for(int j=1; j<length; j++) {
            if(dp[j].second>=max_value) {
                if(dp[j].second==max_value && dp[j].first>=cnt) {
                    continue;
                }
                index = j;
                max_value = dp[j].second;
                cnt = dp[j].first;
            }
        }
        sum += max_value;
        ans[i] = {index+1-cnt+1, index+1};
    }
    
    // 출력
    cout << sum << "\n";
    for(ci i : ans) {
        cout << i.first << " " << i.second << "\n";
    }
    
    return 0;
}