백준 10427 빚

https://www.acmicpc.net/problem/10427

#include <iostream>
#include <vector>
#include <algorithm>

#define INF 987654321

using namespace std;


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    for (int test = 0; test < t; test++) {

        int n;
        long long ans = 0;
        cin >> n;

        vector<long long> arr(n+1);
        vector<long long> prefix(n+1);


        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }

        sort(arr.begin(), arr.end());

        for (int i = 1; i <= n; i++) {

            prefix[i] = prefix[i - 1] + arr[i];

        }



        for (int i = 1; i <= n; i++) {           //가장 많이 빌린 돈
            long long temp = INF;
            for (int j = i; j <= n; j++) {
                //가장 많은 돈을 빌렸을 때 빌린 돈*M-빌린 돈의 합=이자
                temp = min(temp, arr[j] * i - prefix[j] + prefix[j - i]);
            }

            ans += temp;
        }

        cout << ans << "\n";


    }

    return 0;
}

 

  그리디+누적 합 문제이다.

 (추가로 갚아야 할 돈)=(가장 많이 빌린 돈)*(빚을 갚는 횟수)-(빌린 돈의 합) 즉, 배열의 부분합이 필요하므록 누적 합을 사용한다.

 

 풀이

        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }

        sort(arr.begin(), arr.end());

        for (int i = 1; i <= n; i++) {

            prefix[i] = prefix[i - 1] + arr[i];

        }

 

 우선 배열을 입력받고 정렬한 후 부분합을 구한다. 추가로 갚아야 할 돈이 최소가 되려면 가장 많이 빌린 돈과 빌린 돈의 합이 최소가 되어야 하기 때문에 배열을 정렬한 후 연산한다.

 

        for (int i = 1; i <= n; i++) {           
            long long temp = INF;
            for (int j = i; j <= n; j++) {
                //가장 많은 돈을 빌렸을 때 빌린 돈*M-빌린 돈의 합=이자
                temp = min(temp, arr[j] * i - prefix[j] + prefix[j - i]);
            }

            ans += temp;
        }

  이후 i부터 j 까지의 돈을 빌렸을 때의 이자를 모두 구하여 최솟값을 추린다. 이를 ans에 더하여 그 값을 출력하면 답을 구할 수 있다.