C++로 모든 작업을 완료하는 데 필요한 최소 시간 구하기

문제 설명

n개의 요소로 이루어진 배열 A와 두 개의 정수 k, x가 주어졌다고 가정해 보겠습니다. i번째 작업을 완료하는 데는 A[i]만큼의 시간이 걸리며, 배열 A는 비내림차순으로 정렬되어 있습니다.

Amal은 최대 k개의 작업을 골라 해당 작업들을 원래 소요 시간인 A[i] 대신 x 단위의 시간으로 처리할 수 있습니다. 단, x는 모든 A[i] 중 최솟값보다 작아야 합니다. 우리의 목표는 Amal이 모든 작업을 완료하는 데 필요한 최소 시간을 구하는 것이며, Amal은 동시에 두 개 이상의 작업을 수행할 수 없습니다.

예를 들어 입력이 A = [3, 6, 7, 10], k = 2, x = 2라고 한다면 출력은 13이 됩니다. 가장 효율적인 방법은 세 번째와 네 번째 작업을 A[2]와 A[3] 대신 각각 x = 2의 시간으로 처리하는 것이기 때문입니다. 따라서 답은 3 + 6 + 2 + 2 = 13이 됩니다.

해결 접근 방식

이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 배열 A가 이미 정렬되어 있으므로, 소요 시간이 가장 긴 작업들, 즉 배열의 뒤쪽에 있는 k개의 작업을 x 시간으로 처리하도록 선택하는 것이 최적의 전략입니다. 나머지 앞부분의 작업들은 원래 소요 시간을 그대로 더하면 됩니다.

구체적인 단계는 다음과 같습니다.

x를 k * x로 초기화합니다. 이는 마지막 k개의 작업을 각각 x 시간씩 처리하는 데 드는 총 시간입니다.
배열 A의 크기를 n이라고 합니다.
i를 0부터 n - k - 1까지 순회하며 A[i] 값을 누적합니다. 이는 앞부분 나머지 작업들의 원래 소요 시간입니다.
누적된 총합을 반환합니다.

x := k * x
n := size of A
for initialize i := 0, when i < n - k, update (increase i by 1), do:
    t := A[i]
    x := x + t
return x

예제 코드

더 나은 이해를 돕기 위해 아래의 C++ 구현 예제를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k, int x){
    x = k * x;
    int n = A.size();
    for (int i = 0; i < n - k; i++){
        int t = A[i];
        x += t;
    }
    return x;
}
int main(){
    vector<int> A = { 3, 6, 7, 10 };
    int k = 2;
    int x = 2;
    cout << solve(A, k, x) << endl;
}

입력

{ 3, 6, 7, 10 }, 2, 2