L. Two Yachts

두 개의 요트가 있고, 요트를 이용하고 싶은 사람들의 예약 정보 시작 날짜, 끝 날짜, 대여 비용이 주어졌을 때, 최대 이윤을 구하는 문제다.

이 문제는 weighted interval scheduling의 확장판으로 two room weighted interval scheduling이다. 만약 요트가 두 개가 아니라 한 개라면 $O(N \lg N)$ Dynamic Programming 으로 해결할 수 있다. 이와 관련된 자료는 구글에 검색하여 쉽게 찾을 수 있다. 편의상 입력으로 주어진 예약(proposal)을 구간으로 표현하겠다.

이 문제를 $O(N^2)$ Dynamic Programming으로 해결할 수 있지만, 제한 시간을 초과한다. 이 방법에 대한 설명은 생략한다. 

문제 입력 형식에 가장 중요한 조건이 적혀있다. 모든 날짜 마다 겹치는 구간의 개수는 100개를 넘지 않는다. 이 조건을 아래와 같은 조건으로 바꿀 수 있다.

겹치는 구간 쌍의 개수는 $100N$ 보다 많지 않다.

증명) 구간 $i$가 있고 구간 $i$ 보다 시작점이 앞서거나 같은 구간 $j$가 구간 $i$와 겹친다고 하자. 구간 $j$는 구간 $i$의 시작점을 항상 지난다. 어떤 지점이라도 지나는 구간 개수가 100개보다 많지 않기 때문에, 이 때 가능한 구간 $j$의 개수는 100개를 넘지 않는다.

구간들을 시작점을 기준으로 오름차순으로 정렬하고 순서대로 번호를 매긴다. 만약 시작점이 같다면 끝점을 기준으로 오름차순 정렬한다. 다이나믹 배열의 정의를 아래와 같이 한다.

D[i][j] = 구간 i부터 구간 N까지 N-i+1개의 구간이 있다고 가정하고, 구간 i와 구간 j가 겹치고, 이들을 포함할 때 최대 이윤

단, i < j

E[i] = 구간 i의 시작점부터 끝까지 포함할 구간을 적절히 선택할 때 최대 이윤

D[i][j] = max(D[j][x] + C[i], C[i] + C[j] + E[y]) 가 된다.

여기서, C[i]는 구간 i를 선택할 때 얻는 이윤이고, x는 구간 j와 겹치면서 구간 i와 겹치지 않는 구간 중 하나이고, y는 구간 i와 겹치지 않는 번호가 가장 작은 구간이다.

E[i] = max(E[i+1], E[z] + C[i], D[i][j]) 가 된다.

여기서, z는 구간 i와 겹치지 않는 번호가 가장 작은 구간이고, j는 구간 i와 겹치면서 번호가 i보다 큰 임의의 한 구간이다.

이와 같이 다이나믹 배열의 정의를 정하고, 점화식을 세우면 총 시간복잡도 $O(KN \lg N)$에 해결 가능하다. 여기서, $K$는 어느 순간 가장 많이 겹치는 구간 개수를 의미한다. 문제의 조건에 따라 $K \leq 100$이다.

#include <stdio.h> #include <map> #include <algorithm> using namespace std; #define MAXN 10004 int T, N; map <int, int> D[MAXN]; int E[MAXN]; struct Z{ int s, e, c; bool operator < (const Z &ot)const{ return s != ot.s ? s < ot.s : e < ot.e; } } A[MAXN]; int find(int x) { int s = 1, e = N, t = N+1; while (s <= e){ int m = (s+e)>>1; if (A[m].s > x) e = m-1, t = m; else s = m+1; } return t; } int dy(int a, int b) { if (b < a || D[a].count(b)) return 0; int &ret = D[a][b]; int t = find(A[b].e); ret = A[a].c + A[b].c + E[t]; t = find(A[a].e); auto it = D[b].lower_bound(t); if (it != D[b].end() && ret < A[a].c + it->second) ret = A[a].c + it->second; return ret; } int main() { int i, j; for (scanf("%d", &T);T--;){ scanf("%d", &N); for (i=1;i<=N;i++) scanf("%d%d%d", &A[i].s, &A[i].e, &A[i].c), D[i].clear(); sort(A+1, A+N+1); E[N+1] = 0; for (i=N;i;i--){ int t = find(A[i].e); E[i] = max(E[i+1], E[t]+A[i].c); for (j=i+1;j<=N&&A[j].s<=A[i].e;j++){ dy(i, j); } int v = 0; for (auto it=D[i].rbegin();it!=D[i].rend();++it){ if (v < it->second) v = it->second; it->second = v; } if (E[i] < v) E[i] = v; } printf("%d\n", E[1]); } }