백준 1517 c++ 풀이

알고리즘 분류: 자료구조, 정렬, 분할정복

코드:

#include <iostream>

using namespace std;

int n;
int A[500000];
int B[500000];

long long solve(int start, int end)
{
    if (start == end) return 0;
    int mid = (start + end) / 2;

    long long ans = solve(start, mid) + solve(mid + 1, end);

    int i = start;
    int j = mid + 1;
    int k = 0;

    while (i <= mid || j <= end)
    {
        if (i <= mid && (j > end || A[i] <= A[j]))
        {
            B[k++] = A[i++];
        }
        else
        {
            // 왼쪽 배열의 남아있는 원소들의 개수
            ans += (long long)(mid - i + 1);
            B[k++] = A[j++];
        }
    }

    for (int i = start; i <= end; i++) {
        A[i] = B[i - start];
    }
    return ans;
}
int main()
{
    cin >> n;

    for (int i = 0; i < n; i++) cin >> A[i];

    long long ans = solve(0, n - 1);

    cout << ans;

    return 0;
}