백준 1797번 C++ 풀이

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

1797번: 균형잡힌 줄서기

 

입력 때문에 공간복잡도 O(n), 시간복잡도 O(nlogn) 이내에 승부를 봐야 하는 문제입니다.

1. 남= 1, 여 = -1 로 해서 부분합을 모두 구합니다.
2. 부분합의 값이 같으면 그 범위는 그룹을 맺을 수 있습니다.
예제의 경우 1, 2, 1, 2, 1, 2, 3 이고,
인덱스 0과 2의 값이 같다는 뜻은, 범위 1..<2 은 서로 짝지을 수 있는 것입니다.

3. 결국 각각 부분합 값이 같은 것들만 쏙쏙 빼놔서 계산하면 됩니다.

위에서 부분합이 1인 것은 1끼리 묶어서, 2인 것은 2끼리 묶어서 기억하면, 모든 경우를 다 셀 수 있습니다.

3. vector[2000000] 을 선언해서 한바퀴 순회하면서, 각각의 부분합 값을 집어 넣습니다. 예를 들어, vector[1+1000000] = {0, 2, 4} 입니다.
4. map을 전부 돌면서 끝값들을 비교해서 최대값을 갱신합니다.

 

 

접근이 어려워서 PS 향유회 분들의 도움을 많이 받았습니다.

 

https://www.notion.so/PS-da8977089c2344dba9bdbc3d0188d286

 

 

제가 방장인 오픈톡방이니 많이 놀러오세요.

 

#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
#include <list>
#include <stack>
#include <set>

using namespace std;

long long n;

vector<pair<long long, int>> v;

long long sum[1000000];

long long minimumValue[1000000 * 2 + 1];
long long maximumValue[1000000 * 2 + 1];
bool hasIndex[1000000 * 2 + 1];

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


    cin >> n;

    for (long long i=0; i<n; i++) {
        int gender, x;
        cin >> gender >> x;
        if (gender == 0) {
            gender = -1;
        }
        v.push_back({x, gender});
    }

    sort(v.begin(), v.end());

    sum[0] = v[0].second;

    for (long long i=1; i<n; i++) {
        sum[i] = sum[i-1] + v[i].second;
    }

//
//    for (long long i=0; i<n; i++) {
//        cout << sum[i] << '\t';
//    }
//
//    cout << '\n';


    for (long long i=0; i<1000000 * 2 + 1; i++) {
        minimumValue[i] = LONG_LONG_MAX;
        maximumValue[i] = LONG_LONG_MIN;
    }


    minimumValue[1000000ll] = -1;
    for (long long i=0; i<n; i++) {
        long long index = sum[i] + 1000000ll;
        hasIndex[index] = true;
        minimumValue[index] = min(minimumValue[index], i);
        maximumValue[index] = max(maximumValue[index], i);
    }

    long long result = 0;

    for (long long i=0; i<1000000 * 2 + 1; i++) {
        if (hasIndex[i]) {
            long long value = i - 1000000ll;
//            cout << value << '\t' << minimumValue[i] << '\t' << maximumValue[i] << '\n';

            if (minimumValue[i] == maximumValue[i]) {
                continue;
            }
            long long distance = v[maximumValue[i]].first - v[minimumValue[i] + 1].first;

            result = max(distance, result);

        }

    }

    cout << result;




    return 0;
}