====== 랜덤 소트 ======

===== 풀이 =====
  * 효율적인 방법이 있을것 같은데 잘 안떠오르는 상황. 근데 문제를 잘 읽어보면 N이 최대 8이다. 아.. 효율적인 방법이 따로 없는게 맞구나. 그냥 8! 개의 모든 가능한 스테이트들의 기댓값을 DP로 구해버리면 된다.
  * 상태는 O(n!)가지이고, 어떤 상태에서 가능한 스왑은 O(n^2)개이므로 O(n!*n^2)에 돌아가는 dp를 짜면 된다.
  * 조금 번거로운것은, bottom-up으로 구현하려면, 인버전이 1개인 상태들, 인버전이 2개인 상태들, ..., 순으로 dp 테이블을 채워줘야 하는데.. 저 상태들을 나열하기가 쉽지 않다. 이럴때는 그냥 top-down 으로 구현하는 것이 편리하다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1521. 랜덤 소트".

- Problem link: https://www.acmicpc.net/problem/1521
- Solution link: http://www.teferi.net/ps/problems/boj/1521

Tags: [dp]
"""

import functools


@functools.cache
def solve_rec(nums):
    l = list(nums)
    count = 0
    tot_swap = 0.0
    for i, nums_i in enumerate(nums):
        for j in range(i + 1, len(nums)):
            if nums_i > nums[j]:
                count += 1
                l[j], l[i] = l[i], l[j]
                tot_swap += 1 + solve_rec(tuple(l))
                l[j], l[i] = l[i], l[j]

    return tot_swap / count if count > 0 else 0.0


def main():
    N = int(input())  # pylint: disable=unused-variable
    nums = [int(x) for x in input().split()]

    print(solve_rec(tuple(nums)))


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_5}}