공부정리

a[i] 앞으로 돌린 후 n번째 위치까지 올리는데 걸리는 횟수를 d[n]이라 하자. ( d[0] = 1 )

a1 a2 a3 a4 a5 가 있을 때 a6가 a4,a5 사이에 있어야 한다면 ( d[4] )

a6을 먼저 맨 앞으로 올린 후 a1을 올리고, a2를 다시 a1,a6 사이로 넣어야 한다. ( a1 -> d[0] )

a2를 a1,a6 사이로 올린 다음에는 a3를 맨 위로 올리고 다시 a3을 a2,a6 사이로 넣어야 한다. ( a2 -> d[1] )

그런식으로 계산해보면

a1 -> d[0]

a2 -> d[1] = a2->d[0] + a1->d[0]

a3 -> d[2] = a3->d[0] + a1->d[0] + a2->d[1]

a4 -> d[3] = a4->d[0] + a1->d[0] + a2->d[1] + a3->d[2]

d[4] = a6->d[0] + a1->d[0] + a2->d[1] + a3->d[2] + a4->d[3]

이 된다.

이걸로 끝이 아니라 같은 원소가 여러개 있을 때를 생각해봐야 한다.

결론부터 말하자면 같은게 k개 있는 원소가 있으면 (k+1)/2^k 를 곱해주면 된다.

같은게 k개 있는 원소가 m개라면 ((k+1)/2^k)^m 을 곱해주면 된다.