안녕하세요,
재재입니다.
BOJ 5012 불만 정렬 문제 풀이입니다.
BOJ 5012 불만 정렬
(1) 문제 설명
분류 : implementation, graph
출처 : https://www.acmicpc.net/problem/5012
올바른 순서가 아닌 임의의 두 원소 \( (a_i > a_j, i < j) \)를 선택하고, 그 위치를 서로 바꿔줍니다.
이렇게 올바른 순서가 아닌 것을 도치(inversion)라고 하며, 도치의 개수는 최대 \( \frac{n(n-1)}{2} \)개 입니다.
현주는 \( a_i > a_j > a_k \)와 \( i < j < k \)를 만족하는 세 원소를 선택한 뒤,
\( a_i > a_j > a_k \)로 순서를 바꾸려고 합니다.
현주가 선택할 수 있는 세 원소의 개수를 구하는 프로그램을 작성해주면 됩니다.
(2) 풀이 도출
inversion을 구하는 문제는, 정렬 이후 binary indexed tree 로 접근해볼 수 있습니다.
이 문제에서는 좌측 방향에서 개수를 누적하는 binary indexed tree와,
우측 방향에서 개수를 누적한 binary indexed tree 를 구성해볼 수 있습니다.
왼쪽에서 오른쪽으로 이동하면서 오른쪽 트리에서 원소를 하나씩 제거하고,
계산 이후에 왼쪽 트리에서 원소를 하나씩 추가하는 방식으로 시도해볼 수 있습니다.
즉, 현재 숫자보다 큰 숫자의 개수를 왼쪽 트리에서 계산,
현재 숫자보다 작은 숫자의 개수를 오른쪽 트리에서 계산해서 곱한 결과를,
계속 더해나가는 방식으로 해결이 가능합니다.
BOJ 5012 불만 정렬