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 3114 사과와 바나나  (0) 2024.06.13
boj 11560 다항식 게임  (0) 2024.06.13
boj 12841 정보대 등산  (0) 2023.07.31
boj 25427 DKSH를 찾아라  (0) 2023.05.21
boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26

+ Recent posts