[문제 설명]
책의 개수 n과 책을 읽는 데에 걸리는 시간 t1, t2, ..., tn이 주어졌을 때, Kotivalo(이하 K)와 Justiina(이하 J)가 모든 책을 읽는 데에 걸리는 시간의 최솟값을 구하는 문제
[해결 방법]
입력받은 수열 t1, t2, ..., tn에 대해 최댓값 M과, 수열의 합 sum을 정의하여 2 × M와 sum 중 큰 값을 출력하였다.
[Correctness]
K와 J가 각각 모든 책을 다 읽는 시간이 sum임은 당연하다. 그렇다면 K와 J가 동시에 읽는다면 어떻게 되는지 확인해보겠다. 우선 수열 $t_1,t_2,...,t_n$을 내림차순으로 정렬시키고 K와 J는 그 순서대로 읽는다고 가정하겠다. K는 $t_1$부터, J는 $t_2$부터 읽는다고 할 때, 모든 i에 대해 $t_i > t_{i + 1}$이므로 J가 현재 읽고 있는 책을 다 읽기 전에 K가 먼저 읽을 수는 없고 $t_i$는 자연수이므로 $t_1$을 제외하고 J가 책을 먼저 읽게 된다.
J가 책을 다 읽었을 때 K가 $t_1$을 다 읽은 경우, J가 $t_1$을 읽고 K는 남은 책들을 읽으므로 서로에게 간섭이 없어 걸리는 시간은 sum이 된다. J가 책을 다 읽었을 때 K가 $t_1$을 다 읽지 못한 경우, $t_1 > \Sigma_{i = 2}^{n} t_i $이므로 서로 $t_1$을 읽는 동안 나머지를 읽으면 된다. 즉 걸리는 시간은 $2 \times t_1$이고, 이는 $2 \times M$이다.
즉, $2 \times M$과 sum 중 큰 값이 해가 된다.
[Time Complexity]
배열의 길이가 n이고 반복문 한 번으로 해결하였으므로 O(n)이다
[소스 코드] / C++
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
int N;
int M = 0;
ll sum = 0;
int books[200000];
cin >> N;
for (int i = 0; i < N; i++) {
cin >> books[i];
M = max(M, books[i]);
sum += books[i];
}
cout << max((ll) M * 2, sum);
return 0;
}