https://www.acmicpc.net/problem/28018
28018번: 시간이 겹칠까?
댓글을 달아준 학생 수 $N$이 주어진다. $(1\leq N\leq 100\,000)$ 다음 $N$개 줄에는 각 학생의 좌석 배정 시각 $S$와 종료 시각 $E$가 주어진다. $(1\leq S\leq E\leq 1\,000\,000)$ 다음 줄에는 특정한 시각의 개수
www.acmicpc.net
특정 시간에 학생이 몇명 채워져 있는지 구하는 문제입니다.
이 문제는 학생들이 머무르는 구간 l ~ r이 주어집니다.
l ~ r 구간을 모두 채워주어야 하며, 매 쿼리의 l ~ r 구간의 누적을 구하면 O(N^2)의 시간이 걸려 TLE가 발생합니다.
매 쿼리마다 누적합을 갱신하지 않고, 시작과 끝에만 표시하여 한꺼번에 누적합을 구할 수 있는 imos 기법을 활용합니다.
학생은 l 시간에 들어와서 r 시간까지 머무릅니다.
따라서 학생이 존재하기 시작하는 l 시간에 +1, 학생이 없는 시간인 r + 1 시간에 -1을 누적합니다.
마지막에 누적합을 갱신하면 O(N) 시간 만으로도 문제를 해결할 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <iostream>
#define MAX 1000001
using namespace std;
int dp[MAX];
int N, M;
void func() {
for (int i = 1; i < MAX; i++) {
dp[i] += dp[i - 1];
}
int x;
cin >> M;
while (M--) {
cin >> x;
cout << dp[x] << '\n';
}
}
void input() {
int l, r;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> l >> r;
dp[l]++;
dp[r + 1]--;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 12841 정보대 등산 (0) | 2023.07.31 |
|---|---|
| boj 25427 DKSH를 찾아라 (0) | 2023.05.21 |
| boj 25682 체스판 다시 칠하기 2 (0) | 2023.02.26 |
| boj 12996 Acka (0) | 2023.01.29 |
| boj 14450 Hoof, Paper, Scissors (Gold) (0) | 2022.12.30 |