[SWEA] 9999. 광고 시간 정하기

date

Aug 3, 2023

slug

decide-ad-time

author

status

Public

문제

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXIvPBC6aqUDFAXR&categoryId=AXIvPBC6aqUDFAXR&categoryType=CODE&problemTitle=광고+시간+정하기&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

풀이

이 문제는 피크 시간대와 가장 많이 겹치는 시간을 찾는 문제입니다.

적절한 t를 정해, t분부터 t+L분까지 지속되는 광고를 올릴 예정입니다. 여기서, 우리는 우선 t를 임의로 정해야 합니다. t는 각 피크 시간대의 si가 될 것입니다. t를 가정해놓으면 t+L분이 어떤 피크 시간대에 해당하는지 알 수 있습니다. 단순히 순차적으로 탐색할 수도 있고(O(N)) 이분탐색으로도 찾을 수 있습니다. 만약 O(N)으로 찾는다면 전체 시간복잡도가 O(N^2)이여서 시간 초과가 날 것입니다. 따라서 우리는 이분탐색으로 찾아야 합니다.

하지만 우리가 궁극적으로 구해야 하는건 겹치는 시간이 얼마나 되는지 입니다. 만약 적절한 t에 대해 해당 t의 피크 시간대와 t+L의 피크 시간대를 구했다고 합시다. 그럼 그 사이에 있는 모든 피크시간대를 탐색하여

겹치는 시간을 구해주어야 합니다. 그러면 O(N^3)까지 갈 수 있습니다. 즉 t의 피크 시간대와 t+L의 피크 시간대를 구하면 O(1)만에 겹치는 시간을 찾을 수 있어야 합니다. 이를 해결하기 위해 누적합을 사용할 수 있습니다.

아래는 이를 구현한 코드입니다.

arr[i].sm += arr[i-1].sm + arr[i].ri - arr[i].le;

누적합을 구해줍니다. 문제에서 ei < si+1 (1 ≤ i < N) 라는 조건을 주었으므로 위와 같이 바로 계산할 수 있습니다.

ll st = arr[i].le, en = st + l;

임의의 t를(여기선 st) 정합니다. en은 L분까지 광고가 끝나는 시점 입니다.


if (arr[n].ri < en) {
    ans = max(ans, arr[n].sm - arr[i-1].sm);
    continue;
}

만약 광고가 끝나는 시점이 매우 길다면 위와 같이 바로 계산해줄 수 있습니다.

int enIdx = bn(en);

광고가 끝나는 index를 찾아줍니다. 여기서 이분탐색을 사용하였습니다. 만약 해당 index를 찾으면 바로 mi를 리턴해줍니다. 이분탐색이 다 끝났는데도 찾지 못했다면, le를 리턴해줍니다. 여기서 le를 리턴해주는 이유는 광고가 끝나는 시점에 피크 시간대가 없으므로, 그 다음 index를 리턴해주기 위함입니다.


if (arr[enIdx].le + 1 <= en and en <= arr[enIdx].ri) {
  ans = max(ans, arr[enIdx-1].sm - arr[i-1].sm + en - arr[enIdx].le);
} else ans = max(ans, arr[enIdx-1].sm - arr[i-1].sm);

해당 index에 실제로 광고가 끝난다면 위와 같이 계산해줍니다. 만약 해당 index에 광고가 끝나는게 아니라면 그 다음 index이므로 위와 같이 계산해줍니다.

코드


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

struct node {
    ll le, ri;
    ll sm;
};

int tc;
int n, l;
node arr[100001];

int bn(ll f) {
    int le = 1, ri = n, mi;

    while(le <= ri) {
        mi = (le + ri) / 2;
        if (arr[mi].le+1 <= f and arr[mi].ri >= f) {
            return mi;
        } else if (arr[mi].ri < f) {
            le = mi + 1;
        } else if (arr[mi].le+1 > f){
            ri = mi - 1;
        }
    }
    return le;
}

void go() {
    memset(arr, 0, sizeof(arr));
    ll ans = 0;
    scanf("%d %d", &l, &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld %lld", &arr[i].le, &arr[i].ri);
        arr[i].sm += arr[i-1].sm + arr[i].ri - arr[i].le; // 피크 시간대의 누적합
    }
    for(int i = 1; i <= n; i++) {
        ll st = arr[i].le, en = st + l; // t를 st라고 가정했을 때 광고가 끝나는건 st+l
        if (arr[n].ri < en) { // 만약 끝나는게 마지막 보다 크다면 바로 계산
            ans = max(ans, arr[n].sm - arr[i-1].sm);
            continue;
        }
        int enIdx = bn(en); // 광고가 시작하는 idx와 끝나는 idx
        if (arr[enIdx].le + 1 <= en and en <= arr[enIdx].ri) { // 해당 idx에 진짜로 있다면
            ans = max(ans, arr[enIdx-1].sm - arr[i-1].sm + en - arr[enIdx].le);
        } else ans = max(ans, arr[enIdx-1].sm - arr[i-1].sm); // 해당 idx가 없다면
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &tc);
    for(int i = 1; i <= tc; i++) {
        printf("#%d ", i);
        go();
    }
}