CSES 2. Reading Books (1632)

출처: https://cses.fi/problemset/task/1631

---

문제 설명

There are n books, and Kotivalo and Justiina are going to read them all. For each book, you know the time it takes to read it.

They both read each book from beginning to end, and they cannot read a book at the same time. What is the minimum total time required?

입력  

The first input line has an integer n: the number of books.

The second line has n integers t_1,t_2,…,t_n : the time required to read each book.

출력  

Print one integer: the minimum total time.

입력 예

3
2 8 3

출력 예

16

제약조건

• 1 <= n <= 2x10^5
• 1 <= t_i <= 10^9

---

문제 풀이 

가장 긴책을 읽는 동안 다른 책들을 모두 읽을 수 있으면, 가장 긴책을 읽는 시간 * 2, 아니면, 나머지 책을 읽는 시간 + 가장 긴책을 읽는 시간이 된다.

프로그램 내용

...
    for (int idx = 0; idx < nBook; idx++)
        long temp=0;
        lBook = max(lBook, temp);
        sumTime += temp;

    if ( lBook > (sumTime - lBook) )
        mTime = 2 * lBook;
    else
        mTime = sumTime;
...

 

Sorting and Searching ( link )