[일반] 백준 줄세우기 이거 증명은 어떻게함?

[익명(175.223)]

https://www.acmicpc.net/problem/2631
갤에 올라왔길래 풀어봤는데 느낌은 lis같아서 써서 맞았는데,
N - Lis갯수가 최소인건 어떻게 증명하면됨?

[익명(175.223)]

https://www.acmicpc.net/problem/2631

[익명(175.113)]

항상 N-lis 개를 만들 수 있다 + k개를 만든다면 lis가 N-k 이상이다

[익명(175.115)]

1. "N - LIS길이"번의 이동으로 정렬시킬 수 있다. 2. "N - LIS길이"보다 적은 이동 횟수 t번으로 정렬이 가능하다고 가정하면, 이동시키지 않는 원소의 개수 N - t가 LIS의 길이보다 크고, 이때 이 원소들은 증가 수열을 이뤄야 해서 모순. 따라서 "N - LIS길이"번의 이동이 최소 횟수

[대학원오지마세요(publfl)]

핵심은 a라는 원소를 빼서 어딘가에 넣으면, 무조건 원하는 위치에 넣을 수 있기 때문에 항상 올바른 위치에 넣을 수 있다는 것임. 그래서, a라는 원소를 빼서 어딘가에 넣는다는 행동대신, a를 그냥 삭제한다는 행동으로 대체해도 문제가 없게됨. 그러면 이 문제가 묻는건 이거로 바뀜: "최소 몇개의 원소를 제거해야 이 배열이 정렬된 상태가 될까요?" 이건 답이 N-LIS길이라는게 쉽게 보이지