Inversion Counting 삼슝

1. L,M 구간에서 발생하는 Inverse Counting 2 M+1, R 구간에서 발생하는 Inverse Counting 3. [L,M] 에서 i가 선택되고, M+1, R에서 j가 선택되는 Inverse Counting 4. Counting 으로 풀이하는 것도 굉장하군....

#include <stdio.h> #pragma warning(disable : 4996) //#define n_max 100001 #define n_max 10 int n; //길의 n int arr[n_max]; int temp[n_max]; long long int merge(int left, int mid, int right) { int l, m, t; long long int result; result = 0; l = t = left; m = mid; while (l <= mid - 1 && m <= right) { if (arr[l] <= arr[m]) { temp[t++] = arr[l++]; } else { temp[t++] = arr[m++]; result += (mid - l); // 변경 될 때, } } while (l <= mid - 1) temp[t++] = arr[l++]; while (m <= right) temp[t++] = arr[m++]; for (l = left; l <= right; l++) arr[l] = temp[l]; return result; } long long int mergeSort(int left, int right) { int mid; long long int result; result = 0; mid = (right + left) / 2; if (left < right) { result = mergeSort(left, mid) + mergeSort(mid + 1, right); result += merge(left, mid + 1, right); } return result; } int main(void) { int test_case; int T; int i; long long int result; //정답 freopen("input.txt", "r", stdin); setbuf(stdout, NULL); scanf("%d", &T); for (test_case = 1; test_case <= T; ++test_case) { scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &arr[i]); result = mergeSort(0, n - 1); printf("#%d %lli\n", test_case, result); } return 0; }

알파고 #include <iostream> #include <stdio.h> using namespace std; //#define MAXNUM 100001 #define MAXNUM 8 int N; int nums[MAXNUM]; int idxtree[MAXNUM]; void Add(int idx, int val) { while (idx <= N) { idxtree[idx] += val; idx += (idx & -idx); } } long long Sum(int idx) { long long sum = 0; while (idx > 0) { sum += idxtree[idx]; idx -= (idx & -idx); } return sum; } int main() { freopen("input.txt", "r", stdin); int T; cin >> T; for (int t = 1; t <= T; t++) { cin >> N; for (int iter = 1; iter <= N; iter++) { scanf("%d", &nums[iter]); idxtree[iter] = 0; } long long result = 0; Add(nums[1], 1); for (int iter = 2; iter <= N; iter++) { int idx = nums[iter]; long long tmp = (iter - 1) - Sum(idx); result += tmp; Add(idx, 1); } cout << "#" << t << " " << result << endl; } return 0; }