한 기계가 있고 , 그 기계가 차례대로 처리해야 할 작업들이 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 , x1 , x2 , ... , xk 라는 작업이 들어있고 이 묶음의 처리를 t 라는 시각에 시작시켰다면 그 묶음 안에 있는 모든 작업들이 끝나는 시각은 t + S + Tx + Tx1 + Tx2 + ... + Txk 가 된다.
앞에서도 말했듯이 , 작업의 결과는 작업 하나가 끝나는 대로 차곡차곡 나오는게 아니라 , 묶음에 있는 모든 작업들이 끝나야 그것들의 결과가 한꺼번에 출력되기 때문이다.
위의 요소(묶음안의 다른 일들 때문에 걸리는 지연시간 , 시동시간)을 고려하여 i 번째 작업이 끝나는 데 실제로 걸리는 시각이 Oi 라면 , 그 작업의 비용은 Oi * Fi 가 된다. Oi 는 시간이 아니라 시각이다. 따라서 Ti가 같은 작업이라도 앞의 묶음 때문에 늦게 시작한 작업은 비용이 커진다.
예를 들어, 해야 할 작업이 5 개 있어 T1 , T2 , T3 , T4 , T5 = (1 , 3 , 4 , 2 ,1) 이며 , F1 , F2 , F3 , F4 , F5=( 3 , 2 , 3 ,3 , 4) 이라고 하자. 그리고 기계의 시동시간은 1 이라고 하자. 만약 이 일들을 {1,2} , {3} , {4,5} 라는 세 묶음으로 분할하면 완료시각인 O1 , O2 , O3 ,O4 , O5 는 차례대로 ( 5, 5 , 10 , 14, 14) 가 된다. 각 작업의 비용은 Fn 을 곱한 ( 15 , 10 , 30 , 42 , 56 ) 이 된다. 따라서 총 작업 비용은 이 비용들의 합인 153 이 된다.
총 비용을 줄이기 위해서는 지연시간이 적도록 작업들을 효율적으로 분할해야 한다. 하지만 묶음의 바뀔 때마다 드는 기계의 시동시간도 고려해야 한다.
기계의 시동시간과 , 각 일들의 처리시간과 비용계수를 입력받아, 가장 적은 분할 비용을 계산하는 프로그램을 작성하시오.
입력 2 50 100 100 100 100 출력 45000 입력 5 1 1 3 3 2 4 3 2 3 1 4 출력 153
출처:ioi 기출