돌 떨어트리기 > 문제은행



문제은행

1436 : 돌 떨어트리기

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 5 회    시도횟수: 11 회   



당신은 N(1≤N≤10)개의 돌을 가지고 있다.

각각의 돌들은 무게 pi와 가격 vi 의 특징을 가지고 있다. (i = 1, ... , N)

당신은 이 돌 들을 통로를 이용하여 두개의 bunker A 또는 B에 떨어뜨려야 한다.

bunker로 보내는 작업과 교환 작업은 아래와 같다.
돌들은 어떤 하나의 bunker로 다른 bunker와의 무게 + D 를 초과할 때까지 계속 떨어진다. 그리고 통로는 다른 bunker 쪽으로 교체된다. 2개의 bunker는 모두 빈 상태이고, bunker A 쪽으로부터 먼저 떨어진다.

모든 돌들이 두개의 bunker 내로 떨어졌을 때, bunker B 안에 있는 돌들의 최대 가격을 구하는 프로그램을 작성하라.




입력은 N+1개의 line으로 구성된다. 첫째 line은 N과 D가 공백으로 구분되어져 주어진다. 그리고 다음 line은 pi와 vi가 각각 공백으로 구분되어져 주어진다.
모든 입력 데이터 (N을 제외한) 은 0~10,000 의 정수이다.




Bunker B에 떨어진 돌들의 최대 가격을 구한다.



4 2 
2 2 
2 2 
1 1 
1 1
3


출처 : NEERC 2001




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