Tape에 데이터 담기

- 입력 D에는 단위 데이터들이 저장되어 있고, 데이터마다 길이(L)와 사용빈도(F)가 저장되어 있다.
- 매번 read한 후에 full rewind 한다고 가정한다.

- 문제의 목표는 read시간의 기대값을 최소화 하는 것.

 * 알고리즘
- 길이가 짧을수록, 빈도가 높을수록 앞부분에 둔다.
- F(i)/L(i) 값이 큰 것부터 앞에 둔다.
 -> F(i) - L(i) , F(i)^2 / L(i) , 등등의 값 또한 사용할 수 있는데 왜 F(i)/L(i) 값을 쓰는것이 가장 좋은가?

 * 증명
- d1,d2,d3,d4,d5,..... dn 순서가 정답이고, F(i)/L(i)가 감소하는 순서가 아니라고 가정하자
 -> 즉, 정답 중에 F(k)/L(k) < F(k+1)/L(k+1)인 k가 적어도 1개 존재한다.

- S' = d1,d2,d3,,,,,,,d(k+1), d(k),,,,,,,,dn 이라고 하자. ( d(k)와 d(k+1)의 순서를 바꾼 것 )
- S의 기대값 t = F(1)*L(1) + F(2)*( L(1)+L(2) ) + F(3)*( L(1)+L(2)+L(3) + ............

.....+ F(k)*( L(1)+L(2)+...+L(k) ) + F(k+1)*( L(1)+L(2)+...+L(k+1) ) + ... + F(n)*( L(1)+L(2)+...+L(n) )

- S'의 기대값 t' =  F(1)*L(1) + F(2)*( L(1)+L(2) ) + F(3)*( L(1)+L(2)+L(3) + ............

.....+ F(k+1)*( L(1)+L(2)+...+L(k-1)+L(k+1) ) + F(k)*( L(1)+L(2)+...+L(k+1) ) + ... + F(n)*( L(1)+L(2)+...+L(n) )

- t - t' = F(k+1)*L(k) - F(k)*L(k+1)
          = L(k)*L(k+1)*( F(k+1)/L(k+1) - F(k)/L(k) ) > 0

- t > t' 이다. 정답의 기대값인 t보다 작은 t' 존재하는 것은 모순이다.
따라서 가정은 거짓이다.


 * F(i)/L(i)값을 쓰는 이유는 기대값을 계산하고 비교하는데에서 F(i)/L(i)값이 등장하기 때문이다.