BOJ 2631

구글 블로그가 에러가 나서 계속 안 들어가진다.
 

그래서 BOJ 2631를 워드에 임시로 적어놓는다.

이 문제는 고민하다가 처음에는 어떤 순열에서 어떤 순열로 변하는 최소의 수를 가지고 동적계획법으로 하면 어떨까 생각했는데 일단 최대 입력만 해도 무려 200… 게다가 순열을 어떻게 상태로 표현할 것인지도..음 그래서 고민하던 중 하늘이 도우신 것 같다. 갑자기 가장 긴 증가 부분수열이 떠올랐다.!!! LIS(Longest Increasing Subsequence)!!!

그렇다!! LIS의 길이를 구하고 그 길이를 빼면 되는 것이다. 한 번 해보겠다.

정답이다! 열심히 하자!