티스토리 뷰

ICPC/2014 대전

L. Two Yachts

전명우 2014.11.10 17:39

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


이 문제는 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$이다.


코드 보기


'ICPC > 2014 대전' 카테고리의 다른 글

L. Two Yachts  (2) 2014.11.10
K. Travel Card  (2) 2014.11.10
J. Tours  (0) 2014.11.10
I. Three Squares  (0) 2014.11.10
H. String Transformation  (0) 2014.11.10
G. Road Repair  (0) 2014.11.10
댓글
  • 프로필사진 비밀댓글입니다 2015.09.17 23:02
  • 프로필사진 전명우 안녕하세요.
    two room WIS 에 대해 기본적으로 O(N^2) 방법은 알고 있다고 가정하고 풀이를 적었습니다.
    이 문제에서는 문제에서 제시한 조건 때문에 O(N^2) 풀이보다 빠른 O(KN lg N) 풀이가 가능한 것이구요.
    때문에, O(N^2) 방법에서 O(KN lg N) 방법으로 넘어가는 과정만 적었습니다.

    사실, O(KN lg N) 풀이와 O(N^2) 풀이가 크게 다르지 않아 참고하면서 풀면 해결하실 수 있을 겁니다.
    2015.07.27 17:29 신고
댓글쓰기 폼