의도된 시간복잡도
🔒시간 제한
1.000 S메모리 제한
512 MB제출 수
1정답 수
1정답률
100.000%
문제 설명
유명한 문제 중 하나인 Inversion Counting 문제를 풀어보자. 모든 원소가 고유한 수열 $a_1, a_2, ... , a_n$에 대해 아래의 값을 구하면 된다.
- $1 ≤ i < j ≤ n$인 순서쌍 $(i, j)$에 대해 $a_i > a_j$를 만족하는 쌍의 개수
입력 설명
첫째 줄에 수열의 길이 $n$이 주어진다. $(2 ≤ n ≤ 2,000)$
둘째 줄에 $a_1, a_2, ... , a_n$이 공백으로 구분되어 주어진다. $(1 ≤ a_i ≤ n)$
출력 설명
첫째 줄에 문제의 정답을 출력한다.
예시 1
입력
7
1 3 7 5 4 2 6
출력
8힌트
$(i, j) = (2, 6), (3, 4), (3, 5), (3, 6), (3, 7), (4, 5), (4, 6), (5, 6)$ 로 총 $8$가지가 있다.
힌트 - 아이템
🔒 힌트 아이템을 사용하여 해금 하실 수 있습니다.
기여
만든 사람 : pill27211