[BOJ 1517 // C++] 버블 소트

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1948번 문제인 임계경로이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1517

1517번: 버블 소트

이 문제는 inversion의 개수를 세는 문제이다. 이번에는 직접 병합정렬(merge sort)를 하면서 inversion의 개수를 직접 세는 방식으로 문제를 풀어보았다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin; using std::cout;

int arr[20][500001]; // [깊이][배열]
long long ans = 0;
void mergesort(int L, int R, int d) {
    if (L == R) {
        arr[d][L] = arr[0][L];
        return;
    }
    else {
        int mid = (L + R) / 2;
        mergesort(L, mid, d + 1); mergesort(mid + 1, R, d + 1);
        int pL = L, pR = mid + 1, index = L;
        while (pL <= mid && pR <= R) {
            if (arr[d + 1][pL] <= arr[d + 1][pR]) {
                arr[d][index] = arr[d + 1][pL]; pL++; index++;
            }
            else {
                arr[d][index] = arr[d + 1][pR]; ans += mid - pL + 1; pR++; index++;
            }
        }
        while (pL <= mid) {
            arr[d][index] = arr[d + 1][pL]; pL++; index++;
        }
        while (pR <= R) {
            arr[d][index] = arr[d + 1][pR]; pR++; index++;
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    for (int i = 1;i <= N;i++) {
        int x; cin >> x; arr[0][i] = x;
    }
    mergesort(1, N, 0);
    cout << ans;
}