추석맞이 POI풀이: Lecture Halls Reservation

문제 링크: https://www.acmicpc.net/problem/8098

문제 요약

n개의 구간이 있다. 각 구간은 (p,k)로 구성되며 각 숫자는 1이상 30000이하이다. 서로 다른 두 구간은 겹치게 선택할 수 없을 때, 선택한 구간들의 전체 길이 합의 최댓값을 구하여라(단, 두 구간에 대해 한 구간의 끝점과 다른 구간의 시작점이 같은 경우는 선택할 수 있다).

풀이

일단 하나의 구간만 놓고 생각해보자. 특정한 한 구간을 골랐을 때, 이 구간을 맨 끝 구간으로 포함하는 길이 합의 최댓값은 어떻게 구할 수 있을까? 간단하게 생각하면, 현재 구간이 (l,r)일 때 1~l까지의 최댓값 + 현재 구간의 길이가 곧 전체 최댓값이 될 것이다.

이러한 논리를 반복적으로 적용하면, 

dp(pos) = 1 ~ pos번째 위치까지만 고려했을 때 전체 길이 합의 최대 

라고 놓고 계산해 볼 수 있다. 이 경우 모든 구간의 최대치가 30000이므로 답은 dp(30000)이 된다. 각 dp(pos) 값은 위에서 언급한 것처럼 각각의 구간 하나 하나에 대해서 고려해주면 구하기가 쉽다. pos에서 끝나는 어떤 구간 (l, pos)가 있다고 가정하자. 이 경우, l~pos까지는 현재 구간으로 덮을 것이므로 선택할 수 없고, 현재 구간을 제외하면 최대한 큰 값을 골라야 답이 될 수 있다. 따라서, 이 구간에 대해서 최댓값은 dp(l) + (pos - l)이 된다. 따라서,  pos에서 끝나는 모든 구간 (l, pos)에 대해 max(dp(l) + (pos - l)). 이 pos에서 끝나는 구간을 하나 선택하는 경우의 최대이고, pos에서 끝나는 구간을 안 고르는 경우도 고려해야 하므로 이 값과 dp(pos-1)중 더 큰 값이 dp(pos)가 된다.

이 과정을 반복해주면 O(n + 30000)에 답을 구할 수 있다. 물론 위치 값이 훨씬 커져서 위치를 기준으로 계산할 수 없다면 쓸 수 없는 방법이지만, 그 경우 각 구간의 끝 지점을 기준으로 정렬해준 후 구간이 있는 위치에 대해서만 비슷한 방식으로 답을 계산해주면 O(nlogn)으로 풀 수 있다. 이게 좀 더 구현이 복잡하고 이 문제는 이 방법을 쓰지 않아도 풀 수 있기 때문에 쓰지 않는 방향으로 해결했다.