[C++][백준 28018] 시간이 겹칠까?

문제

접근 방법

N개의 입력을 받을 때 S와 E만큼의 범위에 1씩 더해준다면 시간 초과가 일어날 것입니다.
시작 지점과 종료 지점이 정해져 있고 S와 E를 몰아서 받는다는 점을 이용하면 매 순간 범위에 1을 더해줄 필요가 없습니다.

코드

#include <iostream>
using namespace std;
int N, S, E, Q, query;
int prefix[1000002];
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    while (N--)
    {
        cin >> S >> E;
        ++prefix[S];
        --prefix[E + 1];
    }

    for (int i = 2; i < 1000001; ++i)
    {
        prefix[i] += prefix[i - 1];
    }

    cin >> Q;
    while (Q--)
    {
        cin >> query;
        cout << prefix[query] << "\n";
    }
    return 0;
}

풀이

누적 합을 활용하면 됩니다.
시작 지점에 1, 종료 지점 뒤에 -1을 더해주면 누적 합을 할 때 시작 지점부터 종료 지점까지 1을 더한다는 것을 알 수 있습니다.

즉 N개의 입력을 받을 땐 시작 지점과 종료 지점에 체크만 해주면 이후 각 시간의 선택할 수 없는 좌석 수는 배열의 크기만큼만 반복문을 돌리면 됩니다.