백준 10090 counting inversions C/C++

Counting Inversions 성공다국어

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

3280

1453

1040

44.597%

문제

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once.

Two integers in а permutation form an inversion, when the bigger one is before the smaller one.

As an example, in the permutation 4 2 7 1 5 6 3, there are 10 inversions in total. They are the following pairs: 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3.

Write program invcnt that computes the number of the inversions in a given permutation.

입력

The value for the number n is written on the first line of the standard input. The permutation is written on the second line: n numbers, delimited by spaces.

출력

Write the count of inversions on the standard output.

제한

• 2 ≤ n ≤ 1000000

예제 입력 1 복사

7
4 2 7 1 5 6 3

예제 출력 1 복사

10

 

 

#include <iostream>


using namespace std;

long long num = 0;

void MergeTwoArea(int arr[], int left, int mid, int right)
{
	
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
		{
			num += (mid - fIdx + 1);
			sortArr[sIdx] = arr[rIdx++];

		}
		sIdx++;
	}

	if (fIdx > mid)
	{
		
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
	
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

void MergeSort(int arr[], int left, int right)
{
	int mid;
	
	if (left < right)
	{
		
		// 중간 지점을 계산한다.
		mid = (left + right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		
		MergeSort(arr, left, mid);
		
		MergeSort(arr, mid + 1, right);

		// 정렬된 두 배열을 병합한다.
		
		MergeTwoArea(arr, left, mid, right);
	}
}


int main(void)
{
	int arr[1000001];
	int N;
	
	cin >> N;

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

	MergeSort(arr, 0, N - 1);
	
	cout << num;
	return 0;
}

 

이 문제에 있어서 젤 중요한 게 마지막에 잘 세줘야 한다는 것이다.

 

while (fIdx <= mid && rIdx <= right)
	{
		
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
		{
			num += (mid - fIdx + 1);
			sortArr[sIdx] = arr[rIdx++];

		}
		sIdx++;
	}

이 코드가 문제의 핵심인데,

 

num+=(mid-fidx+1) 여기를 해야 한다.

 

만약 왼쪽 값이 더 크다면, 오른쪽 값은 계속 inversion이 일어난다. 이를 넣어줘야한다.

 

표로 이해하자면, 10은 13과 바뀌고, 15와 바뀌고 22와 바뀐다. 

병합정렬로 단순하게 생각하면 그냥 1번 바뀐다고 생각하겠지만, 실제로는 3번이다.

 

12도 마찬가지로 13,15, 22와 inversion이 일어난다.

이것을 표현해주는 식이다.

 

그리고 마지막에 출력을 long long으로 안하면 틀린다.