전시장에서 그림을 판매하는 업체에 하나의 전시대가 배정된다. 전시될 그림은 직사각형의 모양을 가지고 있고, 그림의 높이는 다를 수 있지만 폭은 모두 동일하다고 가정한다. 각 그림에는 가격이 매겨져 있다.
업체는 그림들을 관람객에게 보이기 위해 전시대에 배치하는데, 전시대의 폭이 그림의 폭과 동일하여 겹쳐서 배치해야만 한다. 예를 들어, 위의 그림은 전시대에 네 개의 그림 A, B, C, D를 C, B, A, D의 순서로 겹쳐서 배치한 상황을 보여준다.
위 그림의 오른쪽 부분은 전시된 그림들의 배치를 옆에서 본 모양을 나타내고, 왼쪽 부분은 배치한 그림들을 앞에서 보아서 관람객들이 보게 될 모양을 나타낸다. 그림 A는 앞의 그림 B때문에 가려져서 관람객에게 전혀 보이지 않고, 부분적으로라도 보이는 그림은 B, C, D 뿐이다.
보이는 부분의 세로 길이가 특정 정수 S이상인 그림만 관람객이 관심을 보이고 사게 된다고 가정한다. 전시된 그림들 중 보이는 부분의 세로 길이가 S이상인 그림을 판매가능 그림이라고 부른다.
그림의 높이와 가격이 주어질 때, 판매가능 그림들의 가격의 합이 최대가 되도록 그림을 배치할 때, 그 최대합을 구하는 프로그램을 작성하시오.
첫째 줄에는 그림의 개수 N (1 ≤ N ≤ 300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정수 H와 C가 빈칸을 사이에 두고 주어진다. 단, 1 ≤ S ≤ H ≤ 20,000,000, 1 ≤ C ≤ 1,000이다.
출력
첫째 줄에 판매가능 그림들의 가격의 합이 최대가 되도록 배치했을 때 그 최대 합을 출력한다.
입력 예시
6 4
15 80
8 230
10 100
17 200
20 75
26 80
출력 예시
510
풀이
우선 DP로 접근해보자. 그림을 높이에 따라 오름차순 정렬한다면, i번째 그림 앞에는 무조건 i번째 그림보다 더 작거나 같은 높이의 그림밖에 없다. DP[i]를 i번째 그림을 반드시 사용할 때의 최대 값의 합으로 정의해보자.
[0, i)의 인덱스의 DP 값 중, i번째 그림과의 높이차가 S 이상이며 그 DP 값이 최대인 인덱스를 j라고 두자. 그렇다면 DP[i] = DP[j] + cost[i]가 성립한다.
...문제는, 이 j를 단순히 찾게 된다면 시간복잡도가 O(N^2)이 되어 버린다. 여기서 두 가지 방법을 사용할 수 있겠다.
내가 처음 떠올린 방법이다. 직전(i-1)의 검색한 최종 인덱스를 j', 그 값을 max(dp[:j'+1])라고 두자. 그렇다면 우리는 [ j', i] 영역에서 조건에 맞는 최댓값을 업데이트할 수 있다. 즉 일일히 초기화하여 영역 내 최댓값을 찾지 말고 직전의 값을 활용할 수 있다(즉 메모이제이션이다). 이 최댓값 검색도 O(N)이 소요되므로, 최종 시간복잡도는 O(N)이다.
DP의 정의를 바꾸어 보자. DP[i]를 i번째 그림까지를 살펴보았을 때의 최대 값의 합으로 정의한다. 즉 이 때는 i번째 그림을 사용하지 않아도 상관이 없다. 이 때 수식은 DP[i] = max(DP[i-1], DP[j] + cost[i])가 된다. 이 DP값은 최적 부분 구조를 완전히 만족한다. 따라서 이분 탐색을 적용할 수 있다. lower bound로 picture[i] - S 이상의 값을 처음 가지는 인덱스를 검사한다면, 그 인덱스 바로 이전이 우리가 찾는 j값이 된다. 시간복잡도는 O(NlogN)이다.
1번으로 풀기도 했고, 1번이 훨씬 더 빠른 속도를 보이긴 하지만... 개인적으로는 2번 풀이가 더 깔끔하다는 느낌이 든다.
풀이 코드
import sys
input = sys.stdin.readline
MAX = float('inf')
N, S = map(int, input().split())
picture_list = [[0, 0]] + sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x : (x[0], -x[1]))
dp = [-MAX]*(N+1)
dp[0] = 0
prev_max, prev_idx = 0, 0
for i in range(1, N+1) :
for j in range(prev_idx, i) :
if picture_list[i][0] - picture_list[j][0] < S :
break
prev_idx = j
prev_max = max(prev_max, dp[j])
dp[i] = max(dp[i], prev_max + picture_list[i][1])
print(max(dp))
