[BOJ/Gold 3] 백준 23295 스터디 시간 정하기 1(C++)

문제 링크

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

23295번: 스터디 시간 정하기 1

 

문제

의찬이는 여러 참가자들을 모아 알고리즘 대회 준비 스터디를 진행하고자 한다. 스터디에 많은 참가자들이 모였지만, 각자 가능한 시간들이 달라 의찬이는 스터디 시간을 정하는데 어려움을 겪고 있다. 의찬이는 바쁘면서도 한가하기 때문에 최대한 다른 참가자들의 시간에 맞춰서 스터디를 진행하고자 한다. T시간 동안 스터디를 진행하고자 할 때 참가자들의 시간 만족도를 구해 시간 만족도가 최대인 시간을 찾아주려고 한다.

시간 만족도는 스터디 시간 동안 각 참가자들이 참여할 수 있는 시간들의 합이다.

예를 들어 스터디를 4시간 동안 진행하려 하고 1번, 2번, 3번 참가자들의 가능한 시간들이 아래 그림과 같다고 하자

 

<그림 1> 참가자별로 스터디가 가능한 시간 예시

 

1번 참가자는 시각 0부터 시각 6까지의 시간에 스터디가 가능하다.

2번 참가자는 시각 1부터 시각 3까지, 시각 4부터 시각 6까지의 시간에 스터디가 가능하다.

3번 참가자는 시각 4부터 시각 8까지의 시간에 스터디가 가능하다.

스터디를 시각 2부터 시각 6까지 진행한다면 시간 만족도는 4 + (1 + 2) + 2 = 9 가 되며, 이는 시간 만족도가 최대인 시간이다.

참가자들이 스터디에 참여할 수 있는 시간들을 입력받아 시간 만족도가 최대인 시간을 찾아 출력한다. 시간 만족도가 최대인 시간이 여러 개라면 시작 시간이 가장 빠른 시간을 출력한다.

입력

첫째 줄에는 스터디에 참가하고자하는 참가자 수 N과 스터디 시간 T가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 100,000)

다음 줄부터 참가하고자 하는 참가자들의 시간 정보가 N개 주어진다.

각 정보의 첫째 줄에는 가능한 시간의 수 K가 주어진다. K는 1이상의 자연수이고 입력받은 모든 K의 합은 500,000을 넘지 않는다.

각 정보의 두번째 줄부터 K개의 줄에 걸쳐 가능한 시간의 시작 시각 Si와 끝나는 시각 Ei가 주어진다. 이때 Ei < Si+1 (1 ≤ i < K)을 만족한다. (0 ≤ Si < Ei ≤ 100,000)

출력

시간 만족도가 최대인 시간을 찾아 시작 시각과 끝나는 시각을 공백 한 칸을 사이에 두고 출력한다. 시간 만족도가 최대인 시간이 여러 개라면 시작 시간이 가장 빠른 시간을 출력한다.

예제 입력 1

3 4
2
0 6
8 12
3
1 3
4 6
7 9
1
4 8

예제 출력 1

2 6

알고리즘 분류

• 누적 합
• 슬라이딩 윈도우

풀이

주어진 시간 정보가 0 3이라면, 1시, 2시, 3시까지 스터디가 가능하다는 뜻이 된다. 따라서 DP[1]을 1 증가시키고 DP[4]를 1 감소시킨다.

이렇게 하면 1에서 3까지 구간의 스터디가 가능한 사람을 1명 추가한 것이다.

이런 식으로 N명의 사람들의 시간 정보를 입력받아 각 시간별로 스터디가 가능한 사람의 수를 기록한다.

이후 T시부터 T시간 동안 스터디가 가능한 사람들의 수를 다 더해 만족도를 구하고, 시간을 1시간씩 뒤로 옮기면서 변하는 만족도를 구하며 만족도의 최댓값을 가지는 시간 정보를 구한다. 만족도의 최댓값을 가지는 시간 정보가 여러 개라면 가장 빠른 시간 정보를 출력한다.

코드

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

using namespace std;
int N, T, K, S, E;
int DP[MAX];
int Sum[MAX];
int Maximum;
pair<int, int> Answer;

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

void settings() {
    for (int i = 1; i < MAX; i++) {
        Sum[i] = Sum[i - 1] + DP[i];
    }
    for (int i = 1; i <= T; i++) {
        Maximum += Sum[i];
    }
    Answer = make_pair(0, T);
    int Now = Maximum;
    for (int i = (T + 1); i < MAX; i++) {
        Now += (Sum[i] - Sum[i - T]);
        if (Maximum < Now) {
            Maximum = Now;
            Answer = make_pair(i - T, i);
        }
    }
}

void find_Answer() {
    cout << Answer.first << " " << Answer.second << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}