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

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

 

2021 아주대학교 프로그래밍 경시대회 APC - Div.1 D번 문제이다. 학회 채점 현황에서 다른 분들이 푼 문제들을 보다가 예전에 배웠던 스위핑 기법을 사용하면 될 것 같아서 바로 풀어보았다.

 

N명의 참가자들이 스터디에 참가 가능한 시간이 주어진다.

스터디는 T시간동안 진행될 때, 시간 만족도가 최대인 시간을 찾는 문제이다.

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

---

풀이

문제에 나와있는 그림을 보면 문제를 이해하기 쉽다.

 

그림은 참가자가 3명이고 각 참가자가 스터디에 참가할 수 있는 시간을 색깔 막대기로 표현한 것이다.

만약 스터디 진행시간(T)이 4시간이라면 시각 2부터 시각 6까지 진행하는 게 시간 만족도가 가장 높은 것을 쉽게 알 수 있다.

마찬가지로, 만약 스터디 진행시간(T)이 5시간이라면 시각 1부터 시각 6까지 진행하는 게 시간 만족도가 가장 높은 것을 쉽게 알 수 있다.

---

위와 같은 그림을 간단하게 나타내기 위해 table이라는 1차원 배열을 만들어보자.

table[i]는 (시각 i ~ 시각 i+1)에 스터디에 참가 가능한 인원의 수이다.

 

어떤 참가자의 스터디에 참가할 수 있는 시작 시각 S와 끝 시각 E가 주어졌을 때, 다음과 같은 코드를 통해 배열의 값을 알맞게 구할 수 있다.

for (ll i = s; i < e; i++) table[i]++;

 

위 작업을 모두 완료하면 그림의 상황을 다음과 같이 배열에 저장할 수 있다.

i	0	1	2	3	4	5	6	7	8
table[i]	1	2	2	1	3	3	1	1	0

 

그러나 모든 참가자별로 S와 E가 주어졌을 때, 위와 같은 반복문으로 배열의 값을 변경하게 되면 엄청난 시간이 소모되어 시간 초과가 난다.

 

이를 해결하기 위해 스위핑 기법을 사용하여 배열에 값을 저장하였다. 결과는 위의 표와 똑같이 나오고, 시간은 훨~씬 덜 걸린다.

 

스위핑 기법을 설명하면 아래와 같다.

스위핑의 원리는 다음과 같다.

시작시각의 값에 +1, 끝 시각의 값에 -1을 한 뒤 왼쪽에서 오른쪽으로 이전 값들을 더해가면 시작점~끝점까지의 값은 1이 되고 끝 점 다음 값은 0이 된다. 

 

예를 들어 시작시각이 0이고, 끝 시각이 6이라면..

 

table[0]의 값을 1 증가시키고, table[6]의 값을 1 감소시킨다. 그러면 다음과 같다.

i	0	1	2	3	4	5	6	7	8
table[i]	1	0	0	0	0	0	-1	0	0

 여기서 우리는 '왼쪽에서 오른쪽으로 쓸기' 그러니까 스위핑 작업을 할 것이다. 스위핑 작업은 왼쪽부터 차례대로 table[i]의 값에 table[i-1]의 값을 더하는 작업이다. 이 작업을 하고 나면 다음과 같다.

i	0	1	2	3	4	5	6	7	8
table[i]	1	1	1	1	1	1	0	0	0

우리가 원하는 배열의 형태를 얻을 수 있다. 

 

 

여러개의 (시작점, 끝점) 쌍이 주어졌을 때도, 모든 시작점의 값을 1씩 증가시키고 끝점의 값을 1씩 감소시킨 뒤, 스위핑 작업을 하게 되면 올바른 결과를 얻게 된다. 신기하다....

---

문제 본문의 예시를 통해 이를 확인해보자!!!

다음과 같은 (시작시각, 끝 시각)의 값이 입력될 것이다.

(0,6), (1,3), (4,6), (4,8)

 

이제 각 값이 입력될 때마다 순서대로 아래 작업을 수행해보자. 

table[s]++;
table[e]--;

 

[1] (0,6)을 입력받고 작업을 수행한 결과

i	0	1	2	3	4	5	6	7	8
table[i]	1	0	0	0	0	0	-1	0	0

[2] (1,3)을 입력받고 작업을 수행한 결과

i	0	1	2	3	4	5	6	7	8
table[i]	1	1	0	-1	0	0	-1	0	0

[3] (4,6)을 입력받고 작업을 수행한 결과

i	0	1	2	3	4	5	6	7	8
table[i]	1	1	0	-1	1	0	-2	0	0

 [4] (4,8)을 입력받고 작업을 수행한 결과

i	0	1	2	3	4	5	6	7	8
table[i]	1	1	0	-1	2	0	-2	0	-1

 

이제 다음과 같은 작업(쓸기)을 수행해보자.

for (ll i = 1; i <= 100000; i++) table[i] += table[i - 1];

 

i	0	1	2	3	4	5	6	7	8
table[i]	1	2	2	1	3	3	1	1	0

놀랍게도 스위핑 기법을 사용하지 않은 것과 같은 결과가 나왔다!!

여러 개를 모두 작업해놨다가 한 번만 쓸어도 올바른 결과가 나오는 것을 위 예시를 통해 확인할 수 있었다.

 

이제 누적합을 구한 다음 시간 만족도가 최대인 구간을 찾으면 끝이다!!

 

---

코드

#include <bits/stdc++.h>
#define INF 9876543210
#define endl '\n'
using namespace std;
using ll = long long;

ll n, t, k, s, e, tmp, ans1, ans2;
ll table[100001];
ll sum[100001];

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

	cin >> n >> t;
	for (ll i = 0; i < n; i++) {
		cin >> k;
		for (ll j = 0; j < k; j++) {
			cin >> s >> e;
			table[s]++;
			table[e]--;
		}
	}
    
	//스위핑
	for (ll i = 1; i <= 100000; i++) table[i] += table[i - 1];

	//누적합 구하는 작업
	//sum[i]는 1부터 i까지의 합이다!
	sum[0] = table[0];
	for (ll i = 1; i <= 100000; i++) sum[i] += sum[i - 1] + table[i];
	
   	//최대인 구간 찾는 과정!
	tmp = sum[t - 1];
	ans1 = 0;
	ans2 = t;
	for (ll i = 1; i <= 100000 - t; i++) {
		if (sum[i + t - 1] - sum[i - 1] > tmp) {
			ans1 = i;
			ans2 = i + t;
		}
		tmp = max(sum[i + t - 1] - sum[i - 1], tmp);
	}
    
	cout << ans1 << ' ' << ans2 << endl;

	return 0;
}