이 튜토리얼에서는 하나의 구간(interval)을 제거한 후 남는 최대 커버리지를 구하는 프로그램을 C++로 작성해 보겠습니다.
문제 정의
N개의 구간과 최대 범위 값 Q가 주어집니다. 우리의 목표는 N개의 구간 중 단 하나를 제거했을 때, 1부터 Q까지 범위에서 커버되는 숫자의 개수가 최대가 되도록 하는 구간을 찾는 것입니다.
접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 각 위치별로 해당 위치를 덮고 있는 구간의 개수를 기록합니다(Mark 배열).
- 전체에서 커버되는 위치의 총 개수를 셉니다.
- 정확히 하나의 구간에만 의존하는 위치(즉, 그 구간을 제거하면 사라지는 위치)의 누적 합(prefix sum)을 계산합니다.
- 각 구간을 제거했을 때 손실되는 위치 수를 누적 합으로 빠르게 구하고, 손실이 가장 적은 구간을 선택합니다.
핵심 아이디어는 구간 i를 제거할 때 감소하는 커버리지 = 오직 구간 i에 의해서만 덮여 있는 위치의 개수라는 점입니다. 이 값을 누적 합 배열을 이용해 O(1) 시간에 계산할 수 있어 전체 시간 복잡도를 O(N·Q)까지 줄일 수 있습니다.
구현 예제
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
// 조건을 만족하는 구간 찾기
void solve(int interval[][2], int N, int Q) {
// 각 위치를 덮는 구간의 개수 기록
int Mark[Q] = { 0 };
for (int i = 0; i < N; i++) {
int l = interval[i][0] - 1;
int r = interval[i][1] - 1;
for (int j = l; j <= r; j++)
Mark[j]++;
}
// 현재 커버된 숫자 개수 세기
int count = 0;
for (int i = 0; i < Q; i++) {
if (Mark[i])
count++;
}
// '단 하나의 구간'으로만 덮인 위치의 누적 합 계산
int count1[Q] = { 0 };
if (Mark[0] == 1)
count1[0] = 1;
for (int i = 1; i < Q; i++) {
if (Mark[i] == 1)
count1[i] = count1[i - 1] + 1;
else
count1[i] = count1[i - 1];
}
// 각 구간을 제거했을 때의 커버리지 비교
int maxindex;
int maxcoverage = 0;
for (int i = 0; i < N; i++) {
int l = interval[i][0] - 1;
int r = interval[i][1] - 1;
int elem1;
if (l != 0)
elem1 = count1[r] - count1[l - 1];
else
elem1 = count1[r];
if (count - elem1 >= maxcoverage) {
maxcoverage = count - elem1;
maxindex = i;
}
}
cout << "Maximum Coverage is " << maxcoverage
<< " after removing interval at index " << maxindex;
}
int main() {
int interval[][2] = {
{ 1, 4 },
{ 4, 5 },
{ 5, 6 },
{ 6, 7 },
{ 3, 5 }
};
int N = sizeof(interval) / sizeof(interval[0]);
int Q = 7;
solve(interval, N, Q);
return 0;
}실행 결과
Maximum Coverage is 7 after removing interval at index 4
결과 분석
예제 입력에서 인덱스 4의 구간 {3, 5}를 제거하면 나머지 네 구간이 1부터 7까지 모든 위치를 완전히 덮게 되어 최대 커버리지 7을 얻습니다. 이처럼 누적 합 기법을 활용하면 각 구간 제거 시의 영향을 효율적으로 평가할 수 있습니다.