2.12.3 Ordering & Exchange Argument

개념

여러 작업의 처리 순서를 정해 비용의 합을 최소화하는 문제에서는 인접한 두 작업의 순서를 비교하여 정렬 기준을 찾을 수 있습니다. 다른 작업의 순서는 고정하고 두 작업만 바꾸었을 때 어떤 순서가 유리한지 계산합니다.

완료 시각의 합을 최소화

모든 작업이 시각 $0$에 준비되어 있고, 한 번에 하나씩 쉬지 않고 처리한다고 합니다. 작업은 도중에 중단하지 않으며, 각 작업의 완료 시각을 모두 더한 값을 최소화하려고 합니다.

처리 시간이 $4$, $1$, $3$인 작업을 이 순서로 수행하면 완료 시각은 $4$, $5$, $8$이므로 합이 $17$입니다. 짧은 작업부터 $1$, $3$, $4$ 순서로 수행하면 완료 시각은 $1$, $4$, $8$이며 합은 $13$입니다. 짧은 작업을 앞에 두면 뒤의 작업들이 기다리는 시간을 줄일 수 있습니다.

인접한 두 작업으로 기준 찾기

인접한 두 작업의 처리 시간을 $a$, $b$라고 하고, 앞선 작업들이 끝난 시각을 $T$라고 합니다.

두 순서의 비용 차이는 다음과 같습니다.

$C_{ab}-C_{ba}=(2T+2a+b)-(2T+2b+a)=a-b.$

$a>b$이면 비용 차이가 양수이므로 $b$를 먼저 처리하는 편이 더 작습니다. $a=b$이면 어느 순서든 같습니다. 따라서 인접한 두 작업은 짧은 작업이 앞에 오도록 배치하는 것이 유리합니다.

두 작업의 비교가 전체 최적해로 이어지는 이유

두 작업보다 앞의 작업들은 순서를 바꾸지 않았으므로 완료 시각이 같습니다. 두 작업을 모두 마친 시각도 어느 순서든 $T+a+b$이므로, 뒤의 작업들의 완료 시각도 같습니다. 전체 비용에서 달라지는 것은 비교한 두 작업의 완료 시각 합뿐입니다.

최적 순서 안에 긴 작업 바로 뒤에 짧은 작업이 있다면, 둘을 바꾸어 전체 비용을 더 줄일 수 있습니다. 이는 처음 순서가 최적이라는 가정과 모순입니다. 따라서 최적 순서는 처리 시간이 비내림차순인 순서, 즉 짧은 작업부터 배치한 순서입니다. 길이가 같은 작업은 어느 쪽을 먼저 배치해도 됩니다.

다른 문제에서 순서 교환 증명하기

1. 문제에서 최소화하거나 최대화하는 값을 식으로 정합니다.
2. 인접한 두 대상 $a$, $b$를 고르고, 두 순서의 비용을 각각 계산합니다.
3. 두 비용의 차이 또는 부등식을 정리하여 어느 순서가 유리한지 구합니다.
4. 순서를 바꾼 뒤에도 문제의 조건을 만족하는지, 앞뒤 대상의 비용에는 어떤 영향이 있는지 확인합니다.
5. 기준과 반대인 인접한 쌍을 교환하면 답이 나빠지지 않으며, 교환을 반복해 정렬된 순서를 만들 수 있음을 보입니다.

이 문제에서는 모든 작업이 처음부터 준비되어 있고 자유롭게 순서를 바꿀 수 있다는 조건을 사용했습니다. 작업마다 시작 가능한 시각이나 선후 관계가 있다면, 순서를 바꾸어도 그 조건을 지키는지부터 확인해야 합니다.

복잡도

작업 수를 $N$이라고 합니다. 정렬한 뒤 처리 시간의 누적 합을 각 작업의 완료 시각으로 더합니다.

예제

문제

시각 $0$에 준비된 작업 $N$개가 있다. 작업을 한 번에 하나씩 쉬지 않고 처리하며, 시작한 작업은 끝날 때까지 중단하지 않는다. 처리 순서를 정하여 모든 작업의 완료 시각 합을 최소화하여라.

입력

첫째 줄에 작업 수 $N$이 주어진다. $1\le N\le100$이다.

둘째 줄에 각 작업의 처리 시간 $t_1,\ldots,t_N$이 공백을 사이에 두고 주어진다. $1\le t_i\le100$이다.

출력

완료 시각 합의 최솟값을 출력한다.