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

병합 정렬에서 두 그룹이 병합되는 과정에서 버블 정렬의 swap이 포함되어 있음을 이용하여 문제를 해결할 수 있습니다.

• 5가 앞의 4개의 데이터보다 작으므로 swap이 4번 일어난것과 동일합니다.

병합하는 과정에서 작은 값이 저장될 때 해당 수의 인덱스와 저장되는 위치의 인덱스 차이를 이용하여 이동한 거리를 알 수 있습니다.

실수

result를 int로 사용하였더니 틀렸습니다.

정답이 int의 범위를 벗어날 수 있으므로 long을 사용해야합니다.

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

using namespace std;

static int N;
static vector<int> A;
static vector<int> B;
static long result = 0;

void merge(int l, int m, int r);
void mergeSort(int l, int r);


int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N;

	A.resize(N);
	B.resize(N);

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

	mergeSort(0, N - 1);

	cout << result;

	return 0;
}


void merge(int l, int m, int r)
{
	int i = l;
	int k = l;
	int j = m + 1;
	while (i <= m && j <= r)
	{
		if (A[i] > A[j])
		{
			B[k] = A[j];
			result += j - k;
			j++; k++;
		}
		else
		{
			B[k] = A[i];
			i++; k++;
		}
	}
	if (i > m)
	{
		for (int p = j; p <= r; p++)
		{
			B[k] = A[p];
			k++;
		}
	}
	else
	{
		for (int p = i; p <= m; p++)
		{
			B[k] = A[p];
			k++;
		}
	}
	for (int p = l; p <= r; p++)
	{
		A[p] = B[p];
	}

}

void mergeSort(int l, int r)
{
	if(r>l)
	{
		int m = (l + r) / 2;
		mergeSort(l, m);
		mergeSort(m+1, r);
		merge(l, m, r);
	}

}