별빛 역전
골드 I의견: 0
천문대의 관측 기록에는 \(N\)개의 별이 발견된 순서대로 적혀 있고, 각 별에는 서로 다를 수도, 같을 수도 있는 밝기 등급 \(a_i\)가 매겨져 있다. 두 별 \(i < j\)에 대해 \(a_i > a_j\)이면, 즉 먼저 기록된 별이 더 어두운(등급이 큰) 별보다 밝다면 이 쌍을 역전 쌍이라 부른다.
기록 전체에서 역전 쌍의 개수를 구하여라.
(주의: 등급 값이 같은 두 별은 역전 쌍이 아니다.)
\(1 \le N \le 100\,000\)
\(-10^9 \le a_i \le 10^9\)
첫째 줄에 별의 개수 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 주어진다.
역전 쌍의 개수를 한 줄에 출력한다.
5
3 1 4 1 53역전 쌍은 \((3,1)\) 두 곳: \((a_1,a_2)\)와 \((a_3=4, a_4=1)\), 그리고 \((a_1=3, a_4=1)\). 총 \(3\)개이다. 값이 같은 \(a_2=a_4=1\) 쌍은 세지 않는다.
4
2 2 2 20모든 값이 같으므로 역전 쌍은 \(0\)개이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
별빛 역전
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
별빛 역전