문제1113--Inversion

1113: Inversion

실행시간 제한: 10 Sec  메모리사용 제한: 128 MB
제출: 5991  통과: 3633
[제출] [채점기록] [묻고답하기]

문제 설명

N개의 정수로 이뤄진 수열 A = { a1, a2, …, aN, }이 주어졌을 때, 1≤i<j≤N 이고 ai>aj을 만족하는 쌍 (i,j)의 개수를 세는 프로그램을 작성하라.

 

입력 설명

입력은 표준 입력(Standard input)으로 이뤄진다.

입력의 첫째 줄에는 N(1≤N≤105)이 입력된다. 둘째 줄에는 a1, a2, …, aN(0≤ai≤109)이 입력된다. ai ai+1 사이에는 공백(white-space)가 한 칸 들어간다. 주어진 형식을 벗어나는 입력은 들어오지 않는다.

 

출력 설명

출력은 표준 출력(Standard output)으로 이뤄진다.

입력 된 수열에 대해 위의 조건을 만족하는 쌍의 개수를 출력한다.

 

입력 예시 Copy

5
2 3 1 5 4

출력 예시 Copy

3

도움

Brute force 기법을 이용할 경우 시간 복잡도가 O(N2) 이므로 제시간 안에 답이 나오지 않는다. Merge sort나 Balanced binary search tree를 이용할 경우 제시간에 답을 구할 수 있다.

C/C++을 사용할 경우 답이 32-bit signed integer 범위를 넘어갈 가능성이 있으며,  64 bit-integer 형식인 'long long'을 사용하면 해결 할 수 있으며 사용법은 다음과 같다.

long long value;
value = 0LL; // 0만을 써도 올바른 값이 들어가나, 뒤에 LL을 붙이는 것을 권장한다. 입/출력을 제외하면 사용법은 int와 동일하다.
scanf("%lld", &value); // 입력은%lld format을 사용한다.
printf("%lld", value); // 출력은 %lld로 format을 사용한다.

출처/분류