[백준] 11399번

그냥 sort를 써서 풀어도 되니만, 지금 Algorithms 시간에 배우고 있는 내용을 복습 및 적용해서 문제를 해결하면 좋을 것 같아서 진행했다.

 

해결법은 우선 오름차순으로 정렬한 후, (n-i)*배열 i인데스 만큼을 계속 더해주면 된다.

sigma sigma 계산 편리하게 하는 느낌?

#include <iostream>


void quickSort(int*, int, int);
int target(int, int, int);
void swap(int&, int&);

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, sum = 0;
    std::cin >> n;
    std::cin.ignore();
    int times[n];
    for (int i = 0; i < n; i++) {
        std::cin >> times[i];
    }

    quickSort(times, 0, n-1);

    for (int i = 0; i < n; i++) {
        sum += times[i] * (n-i);
    }
    std::cout << sum << std::endl;
}

void quickSort(int arr[], int left, int right) {
    if (left < right) {
        int t = target(left, right, (left+right)/2);
        int l = left+1, r = right;
        swap(arr[left], arr[t]);

        while (l <= r) {
            if (arr[l] > arr[left] && arr[r] < arr[left]) {
                swap(arr[l], arr[r]);
                l++;
                r--;
            }
            if (arr[l] <= arr[left]) {
                l++;
            }
            if (arr[r] >= arr[left]) {
                r--;
            }
        }
        swap(arr[r], arr[left]);
        quickSort(arr, left, r-1);
        quickSort(arr, r+1, right);
    }
}

int target(int a, int b, int c) {
    if ((a > b && b > c) || (b > a && a > c)) {
        return c;
    } else if (a > b && b < c) {
        return b;
    } else {
        return a;
    }
}

void swap(int& a, int& b) {
    int t = a;
    a = b;
    b = t;
}