컨베이어 벨트

링크 : http://211.228.163.31/pool/coci_traka/coci_traka.php?pname=coci_traka

 

Solution

 

1)   O(NM)

 

D(j) = j번째 사람이 첫번째 작업을 시작할 최소시간

이라 정의하자.

 

그러면 모든 i에 대하여

 

D(j) + {T(1)+T(2)+T(3)...+T(i)}*F(j) <= D(j+1) + {T(1)+T(2)+T(3)...+T(i-1)}*F(j+1) 이 성립해야 한다.

 

즉 모든 작업i에 대해서 j+1번째 사람이 i번째 작업을 시작할 시간은 j번째 사람이 i번째 작업을 끝낸 시간보다 같거나 커야한다.

 

위식을 정리하면

 

모든 i에 대해서

D(j+1) >= D(j) + {T(1)+T(2)+T(3)...+T(i-1)}{F(j)-F(j+1)} + T(i)*F(j)

가 성립해야한다.

 

즉

D(j+1) = D(j) + max( {T(1)+T(2)+T(3)...+T(i-1)}{F(j)-F(j+1)} + T(i)*F(j) )

라는 식을 얻어낼수 있다.

 

 

따라서 모든j에 대해서 모든 i를 훑으면, O(NM)솔루션을 얻어낼수 있다.

 

2) O(NlgM)

 

다음과 같은 함수를 정의하자

C(i,j) = {T(1)+T(2)+T(3)...+T(i-1)}{F(j)-F(j+1)} + T(i)*F(j)

즉, D(j+1) = D(j) + max( C(i,j) ) 이다

 

1 <= i1 < i2 <= M 에 대해서 C(i1,j) <= C(i2,j) 일 필요충분 조건을 구해보자

 

C(i1,j) <= C(i2,j)

 

<==>  {T(1)+T(2)+T(3)...+T(i1-1)}{F(j)-F(j+1)} + T(i1)*F(j) <= {T(1)+T(2)+T(3)...+T(i2-1)}{F(j)-F(j+1)} + T(i2)*F(j)

 

<==> F(j){T(i1)-T(i2)} <= {F(j)-F(j+1)}{T(i1)+T(i1+1) ... + T(i2-2) + T(i2-1)}

 

<==>

 

 

 

<==>

 

  

 

여기서 복잡한 식을 간단히 하기위해 다음과같은 함수를 정의한다

 

 

 

 

그러면 다음과 같은 결론을 얻을수 있다.

 

 

 

위의 결론을 바탕으로 몇가지 정보를 얻어낼수 있다.

 

(i1<i2<i3)에서

i) f(j) <= t(i1,i2) <= t(i2,i3) <==>  C(i1,j) <= C(i2,j) <= C(i3,j)

즉 고정된 j에 대해서 i1과 i2는 고려 할 필요 없는 선택지이다.

 

ii) t(i1,i2) <= f(j) <= t(i2,i3) <==>  C(i1,j) >= C(i2,j) & C(i2,j) <= C(i3,j)

즉 고정된 j에 대해서 i2는 고려 할 필요 없는 선택지이다.

 

iii) t(i1,i2) <= t(i2,i3) <= f(j)  <==>  C(i1,j) >=  C(i2,j) >= C(i3,j)

즉 고정된 j에 대해서 i2와 i3는 고려 할 필요 없는 선택지이다.

 

위 3가지 정보를 결합하면 f(j)값이 증가하든지 감소하든지에 상관없이 t(i1,i2) <= t(i2,i3)가 성립한다면, i2는 필요없는 선택지이다.

 

f(j) 값에 관계가 없기 때문에 j1<j2 에서 j1에서 제거된 i의 리스트는 j2에서 또한 필요없는 리스트가 된다. 즉 리스트에 한번빠진 i의 후보는 다시 추가될 필요없다.

 

그렇다면 이렇게 남은 i의 후보를 L1,L2,L3...Lk라고 하면

 

t(L1,L2) > t(L2,L3) > t(L3,L4) ... > t(L(k-1),Lk) 가 성립한다.

 

만약 (1<=p<k)인 p에 대해서

t(L1,L2) > t(L2,L3) > t(L3,L4) ... > t(L(p-1),Lp) >= f(j) > t(Lp,L(p+1) ... > t(L(k-1),Lk)

가 성립하면

 

C(L1,j) < C(L2,j) ... < C(L(p-1),j) < C(Lp,j) > C(L(p+1),j) > ... > C(L(k-1),j) > C(Lk,j)

가 성립한다

 

즉,

D(j+1) = D(j) + C(Lp,j)이며,

p의 위치는 모든 j 에 대해서 binary search로 log복잡도 만에 찾을수 있음으로

최종적인 알고리즘의 시간복잡도는 O(NlgM)가 된다