Problem Solving/KOITP
술 약속 - SDS_PRO_6_6
hongjun7
2017. 1. 24. 23:15
문제 링크(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)가 되도록 정렬하고 순서대로 계산하면 된다.