[백준-23295] 스터디 시간 정하기 1

해당 문제는 아주대 프로그래밍 경시대회 div 1 문제 였다.

대회 때 문제를 보자마자 누적합이라는 걸 캐치한 뒤 빠르게 푼 기억이 있다.

일단 문제를 푸는 로직은 다음과 같다. 입력받는 스터디 시간들을 +1 -1 prefix 로직을 통해 체킹을 해준다. 체킹을 모두 완료한 뒤에 각각 시간대의 사람 수를 계산하고, 그 계산한 값으로 누적합 배열을 초기화해준다.

위 과정을 통해 누적합 배열을 초기화해주었다면 그 다음에는 m 만큼의 슬라이딩 윈도우를 만들어 O(N)의 복잡도로 가장 많은 사람들이 있는 시간 구역을 찾으면 끝이다.

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
LL arr[200000];
LL cnt[200000];
LL sum[200000];

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

    int n, m;
    cin >> n >> m;

    LL tc, fr, to, max_time = 0;
    for (int i = 0; i < n; i++) {
        cin >> tc;
        for (int j = 0; j < tc; j++) {
            cin >> fr >> to;
            arr[fr] += 1;
            arr[to] -= 1;
            max_time = max(max_time, to);
        }
    }
    cnt[0] = arr[0];
    sum[0] = arr[0];
    for (int i = 1; i <= max_time; i++) {
        cnt[i] = cnt[i - 1] + arr[i];
        sum[i] = sum[i - 1] + cnt[i];
    }

    LL max_cnt = 0, clo = 0;
    for (LL lo = 0; lo <= max_time; lo++) {
        LL calc;
        if (lo == 0) {
            calc = sum[lo + m] - cnt[lo + m];
        }
        else {
            calc = sum[lo + m] - sum[lo - 1] - cnt[lo+m];
        }
        if (calc > max_cnt) {
            max_cnt = calc;
            clo = lo;
        }
    }
    cout << clo << " " << clo + m;
}

 

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

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