백준 15554 <전시회> C++

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

15554번: 전시회

---

 

 

우선 최대 무게와 최소 무게를 지정했다고 가정하겠습니다.

그렇다면 두 미술품 사이에 정렬되어 있는 미술품은 모두 전시하는 것이 S - (A_max - A_min) 의 값을 크게 만듭니다.

A_max 와 A_min 은 고정되어 있는 반면 S 는 값이 커지기 때문입니다.

그렇다면 어느 미술품을 고를 때, 크기별로 정렬되어 있다면 연속된 구간을 모두 선택하는 것이 최적의 해를 구하는 방법이라고 할 수 있습니다.

 

그렇다면 미술품이 크기별로 정렬이 되어있다고 가정했을 때, 

prefixSum : 가치를 누적합한 어레이

i : 크기가 최대인 인덱스

j : 크기가 최소인 인덱스

라고 하겠습니다.

누적합은 어느 구간의 합을 구할 때 좋은 퍼포먼스를 가지므로 사용하겠습니다.

 

S = PrefixSum[i] - PrefixSum[j] 라고 할 수 있으므로

S - (A_max - A_min)

= PrefixSum[i] - PrefixSum[j] - (A_max - A_min)

= PrefixSum[i] - A_i - (PrefixSum[j-1] - A_j) 의 식이 성립합니다. (i = max, j = min)

 

위의 식을 i 에 대한 식과 j 에 대한 식으로 나누고 (i>= j) 라는 조건을 생각할 수 있습니다.

즉,

식 i : PrefixSum[i] - A_i

식 j : PrefixSum[j-1] - A_j

입니다.

 

식 i - 식 j 가 최대가 되는 경우를 구해야 하는데,

식 i 가 증가하고 있거나 식 j 가 감소하고 있을 때 모두 가능성이 존재하므로 두 경우를 모두 고려해주면 됩니다.

다만 ( i >= j ) 라는 조건이 있기 때문에

식 i 의 역대 최댓값과 식 j 의 역대 최솟값이 아닌

식 i 의 현재 값과 식 j 의 역대 최솟값

을 계산해주면 됩니다.

역대 식 i 의 최솟값일 때 i 가 현재 j 보다 크다는 보장이 없기 때문입니다.

---

#include <iostream>

#include <array>

#include <vector>

#include <algorithm>

#include <limits>

using namespace std;

// 정렬 함수, 1순위 : 무게 , 2순위 : 가치

bool sort_prefix(array<long long int, 2>& arr_1, array<long long int, 2>& arr_2) {

    if (arr_1[0] < arr_2[0]) return true;

    else if (arr_1[0] == arr_2[0] and arr_1[1] < arr_2[1]) return true;

    else return false;

}

int main(void) {

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    // 입력

    int N;

    cin >> N;

    array<array<long long int, 2>, 500001> art_arr{};

    for (int i = 1; i <= N; i++) {

        cin >> art_arr[i][0] >> art_arr[i][1];

    }

    // 크기별로 정렬

    sort(art_arr.begin() + 1, art_arr.begin() + N + 1, sort_prefix);

    // 누적합 리스트로 치환

    for (int i = 1; i <= N; i++) {

        art_arr[i][1] += art_arr[i - 1][1];

    }

    //// 이전 i 식의 값, 이전 j 식의 값, j 식의 최솟값 구하기

    // 이전 i 식의 값

    long long int before_i = numeric_limits<long long int>::min();

    // 이전 j 식의 값

    long long int before_j = numeric_limits<long long int>::max();

    // j 식의 최솟값

    long long int min_j = numeric_limits<long long int>::max();

    // 전체 식의 최댓값

    long long int max_all{};

    // 순회

    for (int i = 1, j = 1; i < N+1; i++, j++) {

        // 후보값

        long long int candid_val_i = art_arr[i][1] - art_arr[i][0];

        long long int candid_val_j = art_arr[j - 1][1] - art_arr[j][0];

        // i 식이 증가중이거나 j 식이 감소중이면

        if (candid_val_i > before_i or candid_val_j < before_j) {

            // 최신화

            min_j = min(candid_val_j, min_j);

            max_all = max(max_all, candid_val_i - min_j);

        }

    }

    cout << max_all;

    return 0;

}