[BOJ/Gold 5] 백준 28018 시간이 겹칠까?(C++)

문제 링크

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

28018번: 시간이 겹칠까?

 

문제

얼마 전 부산대학교 커뮤니티에 어느 시간대에 도서관의 열람실 좌석이 널널한지에 관한 질문 글이 올라왔다.

작성자는 지난주 일요일에 언제 도서관의 열람실을 이용했는지 댓글을 달아달라고 부탁하였다.

이에 많은 학생이 본인이 있던 시간을 댓글로 달아주었다.

자랑스러운 부산대학교 학생들은 공부하는 시간에는 도서관에 배정된 자신의 좌석을 비우지 않는다.

각 좌석은 사용이 종료되는 시각에 곧바로 선택될 수 없다.

편의상 시각은 0부터 1,000,000까지 주어지며 정수 단위로 구분된다. 특정한 시각에 선택할 수 없는 좌석이 몇 개였는지 알아보자.

입력

댓글을 달아준 학생 수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개 줄에는 각 학생의 좌석 배정 시각 S와 종료 시각 가 주어진다. (1 ≤ S ≤ E ≤ 1,000,000)

다음 줄에는 특정한 시각의 개수 Q가 주어진다. (1 ≤ N ≤ 100,000)

다음 줄에는 알고자 하는 특정 시각 Q개가 주어진다.

출력

특정 시각에 선택할 수 없는 좌석 수를 주어진 순서에 따라 줄마다 출력하라.

예제 입력 1

1
1 3
2
2 4

예제 출력 1

1
0

예제 입력 2

2
1 5
3 6
3
2 3 7

예제 출력 2

1
2
0

알고리즘 분류

• 누적 합

풀이

특정 시간의 좌석에 대한 변화량을 기록한다.

시간 구간 S, E를 입력받으면, DP[S]를 1 증가시키고 DP[E + 1]를 1 감소시킨다.

이것은 시간 S가 되었을 때 좌석의 개수가 증가했고, 시간 E가 끝났을 때 좌석의 개수가 감소했다는 것을 의미한다.

N개의 시간 정보를 입력받아 변화량을 전부 기록했다면 누적 합을 이용하여 특정 시간에 이용할 수 없는 좌석의 개수를 구할 수 있다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, Q, S, E;
int DP[MAX];
int Sum[MAX];

void settings() {
    for (int i = 1; i < MAX; i++) {
        Sum[i] = Sum[i - 1] + DP[i];
    }
}

void find_Answer() {
    cout << Sum[S] << "\n";
}

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> S >> E;
        DP[S]++;
        DP[E + 1]--;
    }
    settings();
    cin >> Q;
    while (Q--) {
        cin >> S;
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}