술 약속 - SDS_PRO_6_6

문제 링크(koitp.org/problem/SDS_PRO_6_6/)

i번째 약속이 j번째 약속 앞에 위치할 때, 그 조건을 알아보자.

A + S*D(i) + (S+T(i))*D(j) ≤ A + S*D(j) + (S+T(j))*D(i)

T(i)D(j) ≤ T(j)D(i)

i와 j 사이에 임의의 약속들이 있어도 도출되는 식은 변함없다.

따라서 i≤j에 대해 T(i)D(j) ≤ T(j)D(i)가 되도록 정렬하고 순서대로 계산하면 된다.