한 기계가 있고, 그 기계가 차례대로 처리해야 할 작업들이 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이 된다.

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

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

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

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

작업분할(Batch Scheduling) timer 1s memory 32MB

작업분할(Batch Scheduling) 1s 32MB