11722 가장 긴 감소하는 부분 수열

PS 짬통/실랜디

kimximya 2023. 8. 27. 09:42

11722번: 가장 긴 감소하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}

www.acmicpc.net

잊을 만 하면 가끔씩 튀어나오는 LIS LDS

항상 까먹으므로 자주 풀어주는게 좋다고 생각

귀찮아서 O(N^2) 으로 품

LIS 핵심은

해당 값이 이전 수열 항들 중 한 항의 값보다 크면

그 해당 하는 항의 dp값에 1을 더하는데

조건 만족하는 항들이 여러개 있으므로, dp값은

dp + 1 값들 중에서 최대 값을 만족시키게 한다

LDS는 LIS의 조건을 반대로 적용시켜주면 됨