2631 줄세우기

1~N 까지의 N개의 숫자를 오름차순으로 정렬해야 한다. 이 때 어떤 숫자를 다른 숫자의 앞이나 뒤에 끼워넣는식으로 정렬을 하려 할 때, 이 횟수의 최솟값을 찾는 문제이다.

꽤나 고생한 문제인데 풀이법은 간단하다.
점점 증가하는 수열의 길이가 가장 긴것을 찾으면 된다. 이어져있는것이 아니라 띄어져있어도 마찬가지인데, 예를들면

3 7 5 2 6 1 4 라고 하면,

3 7
3 5 6
5 6
2 6
2 4
1 4

이런식으로 증가하는걸 찾았을 때 가장 긴것의 길이, 즉 위 경우에선 3이 나온다.
이 말은 이미 정렬되어있는게 3개라는 뜻이므로 나머지 4개만 끼워넣으면 된다.
따라서 이 예제의 답은 4이다.

위와같은 방법으로 답을 구해주면 된다. 길이를 구해주는것은 재귀와 DP를 이용하였다.

소스