폴리매스

원형파이는 어린 친구 N명을 데리고 소풍을 가려고 한다.

어린친구들에게 줄을 맞춰서 가자고 1부터 N까지의 수가 적힌 작은 이름표를 각각의 친구들에게 나눠주었고, 그 수에 따라 1부터 N까지 줄을 서서 간다고 했다.

출발 전에 줄을 맞게 섰는지 확인한 뒤 출발했다.

출발한지 30분이 된 순간에 원형파이는 다시 줄을 잘 서서 오고 있는지 확인을 했다.

그러나 어린 친구들이라서 그런지 줄이 엉망이 되었다.

어린 친구들을 앞에서부터 자신의 이름표에 적힌 수들을 작은 종이에 차례차례 적었다.

원형파이는 한 어린 친구를 줄에서 빼낸 뒤에 원하는 위치에 넣을 수 있다.

그런데 한가지 조건은, 어린 친구들은 최대한 움직이지 않기를 원하기 때문에 어린 친구들은 최소로만 해서 움직이게 하자.

종이에 적힌 수들이 다음과 같을 때 최대 몇 명의 친구들의 위치를 옮겨야 할지를 점화식으로 구하여라.

(1) 3 7 5 2 6 1 4

(2) 1 2 3 4 5 6 7 8 9 10

(3) 5 1 8 7 2 3 4 9 6 10

(4) 4 5 10 3 2 1 7 8 9 6

(5) 1 9 6 4 8 2 3 7 5 10

(6) 3 1 4 8 10 5 7 6 9 2 20 14 15 13 11 17 12 19 16 18

(풀이과정은 필수입니다)