Created at : 2024-05-12 17:41
3020

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, H;
    cin >> N >> H;
    vector<int> Top(H + 1, 0), Bottom(H + 1, 0);
    for(int i = 0; i < N / 2; ++i)
    {
        int B, T;
        cin >> B >> T;
        ++Bottom[B];
        ++Top[H - T + 1];
    }

    for(int i = 1; i < H; ++i)
    {
        Bottom[H - i] += Bottom[H - i + 1];
        Top[i + 1] += Top[i];
    }

    int MinCollision = INT32_MAX, Count = 0;
    for(int i = 1; i <= H; ++i)
    {
        int Collision = Top[i] + Bottom[i];
        if(MinCollision > Collision)
        {
            MinCollision = Collision;
            Count = 1;
        }
        else if(MinCollision == Collision)
        {
            ++Count;
        }
    }
    cout << MinCollision << ' ' << Count;

    return 0;
}

문제의 답인 장애물의 최솟값과 구간의 수는 직관적으로 1번구간부터 H번 구간까지 O(N) 로 구하면 된다. 하지만 문제는 각 구간별 장애물의 수를 O(N^2) 로 구할 경우 시간초과가 나기 때문에, 누적 합을 이용하여 O(N) 로 구해주면 된다.

기본 아이디어는 석순과 종유석 각각 따로 저장을 한다. 저장을 할때에는 끝부분에만 +1을 해준다. 무슨 소리인지 예제 입력1로 알아보자

• 예제 입력1

6 7
1
5
3
3
5
1

종유석(아랫부분, 홀수)만 보았을때, 높이는 각각 1, 3, 5이다. 여기서 끝부분에만 +1을 해 준다는 것은 종유석을 높이별로 갯수를 저장하는 배열을 Bottom이라고 할때, Bttom[1], [3], [5] 은 1이 되고 나머지는 0이 된다. 그리고 위에서 부터, 즉 Bottom[6] 에서 부터 Bottom[i] += Bottom[i + 1] 을 해준다는 것이다.
석순도 똑같이 진행해 주면 된다.

유형

누적 합
이분 탐색