백준 23301 (C++) 스터디 시간 정하기 2

최초 업로드: 2025-09-27 12:27:48

최근 수정 시간: 2025-09-27 12:27:48

게시자: rlatjwls3333

카테고리: 백준

# [Silver IV] 스터디 시간 정하기 2

[문제 링크](https://www.acmicpc.net/problem/23301)

## 문제 설명

의찬이는 여러 참가자들을 모아 알고리즘 대회 준비 스터디를 진행하고자 한다. 스터디에 많은 참가자들이 모였지만, 각자 가능한 시간들이 달라 의찬이는 스터디 시간을 정하는데 어려움을 겪고 있다. 의찬이는 바쁘면서도 한가하기 때문에 최대한 다른 참가자들의 시간에 맞춰서 스터디를 진행하고자 한다. 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 ≤ 1000, 1 ≤ T ≤ 1000)

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

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

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

## 출력

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

## 풀이
imos로 만족도를 미리 구해 놓고, 슬라이딩 윈도우로 답을 구했습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int cnt[1002];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, t; cin >> n >> t;
    while(n--) {
        int k; cin >> k;
        while(k--) {
            int s, e; cin >> s >> e;
            cnt[s]++;
            cnt[e]--;
        }
    }

for(int i=1;i<=1000;i++) cnt[i] += cnt[i-1];

int res=0, a, b, sum=0, l=0, r=0;
 while(r<1000) {
 sum += cnt[r++];
 if(r-l>t) sum -= cnt[l++];
 if(res<sum) {
 res=sum;
 a=l;
 b=r;
 }
 }
 cout << a << ' ' << b;
}
```