[백준 14002: JAVA] 가장 긴 증가하는 부분 수열 4/ 동적 프로그래밍 + 역추적
개요 이 문제는 dp와 이분 탐색으로 풀이할 수 있다. 하지만 문제의 입력의 최댓값이 1000이기 때문에 나는 dp로 풀이할 것이다. dp로 풀이할 때는 이전에 구한 값을 통해 풀이하게 된다. 또한 시간은 O(n^2)이 될 것이다. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 풀이 dp[i] = k → i번째 수열까지의 최대 증가수열의 길이 = k 라고 생각하고 접근하면 된다. 예를 들어 수열 {1, 2, 1, 3, 4, 3}이 주어지고 인덱스가 1부터 시작하여 6까지 ..
