1517번 버블소트

 버블 소트를 실행했을 때 swap한 횟수를 구하면 된다.

 

 버블 소트를 그대로 구하면 시간 초과가 발생한다(시간 복잡도 O(n^2)이기 때문에)

 

 머지 소트를 이용해 swap하는 횟수를 구하면 된다.

 

 ex) 5 4 3 2 1     

  -> 4 5 3 2 1     5와 4를 비교하여 1번 이동

  -> 3 4 5 2 1     3과 4,5를 비교하여 3이 2번 이동

  -> 3 4 5 1 2     1과 2를 비교하여 1번 이동

  -> 1 2 3 4 5     1과 3,4,5를 비교하여 3번 이동 + 2와 3,4,5를 비교하여 3번 이동

 총 1+2+1+3+3 = 10번 이동을 하게 된다.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int N;
vector<long> A;
vector<long> sorted;
long ans;
 
void Merge(long start, long mid, long end){
    long i=start;
    long j=mid+1;
    long k=start;
    
    while(i<=mid && j<=end){
        if(A[i]>A[j]){
            ans+=(mid-i+1);
            sorted[k++]=A[j++];
        }
        else{
            sorted[k++]=A[i++];
        }
    }
    if(i>mid){
        for(long l=j;l<=end;l++){
            sorted[k++]=A[l];
        }
    }
    else{
        for(long l=i;l<=mid;l++){
            sorted[k++]=A[l];
        }
    }
    
    for(unsigned long l=start;l<=end;l++){
        A[l]=sorted[l];
    }
}
 
void MergeSort(long start, long end){
    long mid;
    
    if(start<end){
        mid=(start+end)/2;
        MergeSort(start,mid);
        MergeSort(mid+1,end);
        Merge(start,mid,end);
    }
}
 
int main(){
    cin >> N;
    
    for(int i=0;i<N;i++){
        long num;
        cin >> num;
        A.push_back(num);
    }
    
    sorted=vector<long> (A.size());
    
    MergeSort(0,A.size()-1);
    
    cout << ans << endl;
}