https://jungol.co.kr/problem/2584
| 시간 제한 | 메모리 제한 |
| 1초 | 64MB |
문제
전시장에서 그림을 판매하는 업체에 하나의 전시대가 배정된다. 전시될 그림은 직사각형의 모양을 가지고 있고, 그림의 높이는 다를 수 있지만 폭은 모두 동일하다고 가정한다. 각 그림에는 가격이 매겨져 있다.
업체는 그림들을 관람객에게 보이기 위해 전시대에 배치하는데, 전시대의 폭이 그림의 폭과 동일하여 겹쳐서 배치해야만 한다. 예를 들어, 위의 그림은 전시대에 네 개의 그림 A, B, C, D를 C, B, A, D의 순서로 겹쳐서 배치한 상황을 보여준다.
위 그림의 오른쪽 부분은 전시된 그림들의 배치를 옆에서 본 모양을 나타내고, 왼쪽 부분은 배치한 그림들을 앞에서 보아서 관람객들이 보게 될 모양을 나타낸다. 그림 A는 앞의 그림 B때문에 가려져서 관람객에게 전혀 보이지 않고, 부분적으로라도 보이는 그림은 B, C, D 뿐이다.
보이는 부분의 세로 길이가 특정 정수 S 이상인 그림만 관람객이 관심을 보이고 사게 된다고 가정한다. 전시된 그림들 중 보이는 부분의 세로 길이가 S 이상인 그림을 판매가능 그림이라고 부른다.
그림의 높이와 가격이 주어질 때, 판매가능 그림들의 가격의 합이 최대가 되도록 그림을 배치할 때, 그 최대합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 그림의 개수 N(1≤N≤300,000)과 판매가능 그림을 정의하는 정수 S가 빈칸을 사이에 두고 주어진다.
다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정수 H와 C가 빈칸을 사이에 두고 주어진다.
단, 1≤H≤20,000,000, 1≤C≤1,000 , 1≤S≤H 이다.
출력
첫째 줄에 판매가능 그림들의 가격의 합이 최대가 되도록 배치했을 때 그 최대 합을 출력한다.
풀이
가려지는 그림들은 아예 배치하지 않아도 됩니다. 즉, 그림의 순서를 정한다기 보다 그림을 선택한다고 생각하는 게 문제 해결 아이디어를 떠올리는 데 좀 더 직관적으로 접근이 됩니다.
먼저 그림들을 높이 오름차순으로 정렬해봅시다. 그리고 높이가 낮은 그림부터 순서대로 확인하며 현재 확인 중인 그림의 높이가 `H`일때 `H-S`보다 크지 않은 그림들을 선택했을 때 최적해를 생각해볼 수 있습니다.
$i$번째 그림을 선택했을 때의 최적해를 `dp[i]`라고 해보겠습니다. `S`보다 높이가 낮은 그림들의 `dp`값은 모두 각 그림의 `C`입니다. 높이가 `S`보다 큰 `x`번째 그림을 선택하는 경우를 생각해봅시다. 높이가 `H-S`보다 크지 않은 모든 그림 중 가장 높이가 높은 그림이 `k`번째 그림이라고 해봅시다. 그럼 `dp[x]`는 높이가 0~`H-S`범위에 있는 모든 그림에 대해 각 그림을 선택한 경우의 최적해인 `max(dp[0]...dp[k])`에 현재 그림인 `x`의 가격 `C`를 더한 값이 됩니다.
dp[x] = max(dp[0]...dp[k]) + C
현재 그림의 높이 `H`보다 `S`이상 만큼 작은 그림의 번호 `idx`는 투 포인터 비슷하게 찾을 수 있습니다.
그리고 `0~idx`범위에서의 최적해는 세그먼트 트리로 관리할 수 있습니다.
`N`개의 그림에 대해 $O(NlogN)$으로 쿼리를 수행하고 $O(logN)$으로 값 갱신을 하면 시간 내에 해결이 가능합니다.
정답 코드
query, update 함수의 코드는 생략합니다.
x = 0
while pic[x][0] < s:
dp[x] = pic[x][1]
update(x, dp[x])
x += 1
idx = 0
for i in range(x, n):
h, c = pic[i]
while h-s >= pic[idx][0]:
idx += 1
dp[i] = query(idx)+c
update(i, dp[i])
print(max(dp))
