돛단배(Sails) > 문제은행



문제은행

2658 : 돛단배(Sails)

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



새로운 해적선을 건조중이다. 

해적선은 N개의 돛대를 가지고 있으며 각각의 돛대는 돛을 매달 수 있도록 만든 일정한 단위길이의 돛 구간으로 나뉘어 있다. 

돛은 모두 같은 크기이며 돛 구간에 꼭 맞는다.
돛대에 매달게 되는 돛은 임의의 돛 구간에 매달릴 수 있지만 하나의 돛 구간에는 하나의 돛만 매달 수 있다.

돛은 바람의 저항으로 이해 추진력을 받으므로 돛 구간에 배치된 돛을 어떻게 배치하느냐에 따라서 서로 다른 추진력을 생성할 수 있다. 

같은 높이의 돛이 다른 돛보다 앞에 있는 경우 바람의 영향을 덜 받게 되어 추진력을 덜 받는다. 이러한 경우를 돛의 비효율 지수라고 하자.

이 배는 6개의 돛대를 가지고 있으며 각 돛대의 높이는 3, 5, 4, 2, 4, 3 이고 앞은 왼쪽 뒤는 오른쪽이다. 

위와 같이 돛대의 배치할 때, 비효율지수의 총합은 10이다.각 돛에 적혀있는 숫자는 각 돛의 비효율 지수이다.

비효율지수의 총합은 각 모든 돛들의 비효율 지수의 합을 의미한다.
N 개의 각 돛대의 높이와 각 돛대에 매달게 되는 돛의 개수가 주어질 때, 비효율 지수의 총합을 최소로 하는 프로그램을 작성하시오.

 

[입력 예 설명]

입력 예를 그림으로 그리면 아래와 같다.

비효율 지수의 총합은 10이다.

d9f31607d4458b170ccda6d01e03c4ae_1550816
 




첫 행에 돛대의 개수 N(2≤N≤100,000)이 주어진다.
이후 N개의 행에 걸쳐 각 돛대의 높이 H(1≤H≤100,000)와 매달게 되는 돛의 수 K(1≤K≤H)가 행으로 구분되어 주어진다. 주어지는 순서대로 1번 돛대부터 N번 돛대까지의 정보이다. 1번 돛대가 맨 앞의 돛대이고 N번 돛대가 맨 뒤의 돛대이다.




비효율 지수의 총합을 최소로 할 때 비효율 지수를 하나의 정수로 출력하시오.
cf) 출력결과는 int 범위를 초과할 수 있다.



6
3 25 34 12 14 33 2
10






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.