전시장 > 문제은행

본문 바로가기


알고리즘 분할정복

2584 : 전시장

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 627회    시도횟수: 2826회   



전시장에서 그림을 판매하는 업체에 하나의 전시대가 배정된다. 전시될 그림은 직사각형의 모양을 가지고 있고, 그림의 높이는 다를 수 있지만 폭은 모두 동일하다고 가정한다. 각 그림에는 가격이 매겨져 있다.


d197a14dbebff04731d95aac334f7c23_1455876
 
업체는 그림들을 관람객에게 보이기 위해 전시대에 배치하는데, 전시대의 폭이 그림의 폭과 동일하여 겹쳐서 배치해야만 한다. 예를 들어, 위의 그림은 전시대에 네 개의 그림 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 이다.


첫째 줄에 판매가능 그림들의 가격의 합이 최대가 되도록 배치했을 때 그 최대 합을 출력한다.

< 테스트 데이터 조건 >
• 전체 테스트 데이터의 20%는 N≤20.
• 전체 테스트 데이터의 60%는 N≤10,000.

[Copy]
6 4
15 80
8 230
10 100
17 200
20 75
26 80
[Copy]
510


[Copy]
9 3
8 30
5 10
14 50
12 80
8 20
16 50
11 60
15 40
10 50
[Copy]
170




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.