IOI 2002 day2 1- 작업분할(Batch Scheduling) > 문제은행 : 정보올림피아드&알고리즘




3503 : 작업분할(Batch Scheduling)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
1 회   
시도횟수
1 회   

문제

한 기계가 있고, 그 기계가 차례대로 처리해야 할 작업들이 N개 있다. 

각 작업들은 1부터 N까지 번호가 매겨져 있다. 

기계 동작의 효율을 위해, 우리는 이 작업들을 하나 이상의 묶음으로 쪼개려고 한다. 

예를 들어 작업이 여섯 개 있으면 {1, 2, 3}, {4}, {5, 6}이나 

{1, 2}, {3, 4, 5}, {6}처럼 작업의 순서만 유지하면 어떤 식이든 가능하다.

 

이들의 처리는 0이라는 최초의 시각에 시작한다. 

기계는 일들을 묶음 단위로 하나씩 처리하는데, 이들을 처리하는 순서 역시, 

번호가 작은 작업들의 묶음부터 하는 걸로 정해져 있다. 

즉 {1, 2} 묶음을 처리하지 않고 {6}부터 먼저 할 수는 없다. 

묶음 안에 있는 작업들은 기계 안에서 순차적으로 처리되나, 

어떤 묶음 안에 한 번 소속된 작업은 그 묶음에 있는 작업들 전체가 처리가 끝나기 전에는 결과가 나오지 못한다. 

따라서 j째 작업의 완성 시간은 j가 속한 묶음 전체의 작업이 완성되는 시간과 같다.

 

첫 묶음의 작업을 시작하기 전에, 

그리고 한 묶음에서 다른 묶음의 작업으로 넘어가기 전에는 기계를 시동시키기 위해 S라는 고정된 시간이 필요하다. 

그리고 임의의 작업(번호가 i라면)을 하는데는 Fi라는 비용 계수와 Ti라는 시간이 필요하다. 

어떤 묶음에 x, x+1, ..., x+k라는 작업이 들어가 있고 이 묶음의 처리를 t라는 시각에 시작시켰다면 

그 묶음 안에 있는 모든 작업들이 끝나는 시각은 t + S + (Tx + Tx+1 + ... + Tx+k)가 된다. 

앞에서 말했듯이, 작업의 결과는 작업 하나가 끝나는 대로 차곡차곡 나오는 게 아니라, 

묶음에 있는 모든 작업들이 끝나야 그것들의 결과가 한꺼번에 출력되기 때문이다.

 

위의 요소(묶음 안의 다른 일들 때문에 걸리는 지연 시간, 시동 시간)를 고려하여 

i째 작업이 끝나는 데 실제로 걸리는 시각이 Oi라면, 

그 작업의 비용은 Oi×Fi가 된다. Oi는 시간이 아니라 시각이다. 

따라서 Ti가 같은 작업이라도 앞의 묶음 때문에 늦게 시작한 작업은 비용이 커진다. 

예를 들어, 해야 할 작업이 다섯 개 있어 (T1, T2, T3, T4, T5) = (1, 3, 4, 2, 1)이며, 

(F1, F2, F3, F4, F5) = (3, 2, 3, 3, 4)이라고 하자. 

그리고 기계의 시동 시간 S는 1이라고 하자. 

만약 이 일들을 {1, 2}, {3}, {4, 5}라는 세 묶음으로 분할하면 완료 시각인 (O1, O2, O3, O4, O5)는 

차례대로 (5, 5, 10, 14, 14)가 된다. 

첫째 묶음의 완료 시각은 S+T1+T2=1+2+2=5이고, 둘째 묶음의 경우는 S+T3=5에다 앞의 5를 더한 10, 

그리고 마지막 묶음의 처리 완료 시각은 S+T4+T5=4에다 10을 더한 14인 것이다. 

그리고 이 작업들의 비용은 각 수에다 Fn을 곱한 (15, 10, 30, 42, 56)이 된다. 

따라서 총 작업 분할 비용은 이 비용들의 합인 153이 된다.

 

총 비용을 줄이기 위해서는 지연 시간이 적도록 작업들을 효율적으로 분할해야 한다. 

하지만 묶음이 바뀔 때마다 드는 기계의 시동 시간도 고려해야 한다. 

기계의 시동 시간과, 각 일들의 처리 시간과 비용 계수를 입력받아, 

있을 수 있는 가장 적은 분할 비용을 계산하는 프로그램을 작성하시오.​ 

 


입력형식

표준 입력 스트림에서 데이터를 읽어들인다. 첫째 줄에는 작업의 총 개수 N이 있다. (1≤N≤10000)

둘째줄에는 묶음이 바뀔 때의 기계 시동 시간인 정수 S가 있다. (0≤S≤50) 

그리고 다음 N줄에는 1, 2, ..., N째 작업에 대해 그 작업의 처리 시간인 Ti와(1≤Ti≤100) 비용 계수인 Fi (1≤Fi≤100)이 순서대로 들어있다.


출력형식

표준 출력 스트림으로 답을 출력한다. 작업 분할 비용의 최소값을 나타내는 자연수 하나를 한 줄에다 출력한다.

채점 과정에서 작업 분할 비용이 231-1을 넘는 일은 발생하지 않는다. 

답안 프로그램이 제한 시간 내에 입력 자료에 대한 맞는 답을 출력하면 만점을 받고, 그렇지 않으면 0점을 받는다.


입력 예

2
50
100 100
100 100

출력 예

45000

입력 예

5
1
1 3
3 2
4 3
2 3
1 4

출력 예

153


DP, CHT

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP