[DP] 백준 11722::가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 11722번 제출 맞은 사람 숏코딩 풀이 풀이 작성 재채점/수정 채점 현황 강의 가장 긴 감소하는 부분 수열 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 10698 6745 5523 64.756% 문제 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30 , 10, 20 , 20, 10 } 이고, 길이는 3이다.

입력 첫째 줄에 수열 A의... www.acmicpc.net LIS 시리즈 N<1000으로 주어지는 값이 매우 작다. O(NlgN)으로도 풀리지만, 2중for문을 이용하여 O(N^2)으로 풀어보자 DP[i] = A[]배열 중 A[i]원소로 끝나는 '감소하는 부분수열'.

길이...