2631번: 줄세우기 www.acmicpc.net 이 문제는 N명의 아이들이 번호순서가 무작위로 바뀐 상태로 줄울 섰을 때 번호 순서대로 배치하기 위해 옮겨야 하는 아이들의 최소 수를 구하는 문제이다. 이를 효율적으로 해결하기 위해서는 우선 그나마 제대로 줄을 선 아이들을 고정시키고, 나머지 아이들을 이 아이들 사이에 넣어야 한다. 예를 들어 아이들이 3 7 5 2 6 1 4 순서로 줄을 섰다고 가정하면 3, 7번 아이들이 그나마 번호 순서대로 섰기에 이를 고정시킨 뒤 나머지 5, 2, 6, 1, 4번 아이들을 순서에 맞게 넣으면 된다. 이 밖에도 3, 5, 6번 아이들을 고정시킨다던가, 2, 4번 아이들을 고정시키는 방법도 있다. 이때 이동하는 아이들을 최소화하기 위해서는 고정시키는 아이들을 최대한 많..