[백준/알고리즘] 14003번 가장 긴 증가하는 부분수열 5 (골드 1)
BOJ 14003번 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이와 수열을 출력하시오. 풀이 알고리즘 : LIS 알고리즘, DP 앞서 LIS의 길이만 출력하는 문제와 다르게, 그 수열을 출력하는 문제이다. LIS를 lower_bound를 이용해 구하면, 그때의 벡터에 들어있는 값은 단순히 길이를 재기위한 값이고, LIS가 아니다.그래서, DP를 통해 해당 수열이 LIS에서 몇번째 인덱스에 위치했었는지를 저장하고, 나중에 역으로 확인해서 출력하면 된다. 예를들면 1, 3, 2, 4, 5 라는 수열이 있다고 하면,i = 0일때 arr[i] = 1이고, lis = []이므로, lis = [1] 이고 따라서 1은 0번째 인덱스에 위치한다고 저장한다.i = 1일때 arr[i] = 3이고, lis =..
