백준 11053번 가장 긴 증가하는 부분 수열 [C++]

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

11053번: 가장 긴 증가하는 부분 수열

이 문제는 Dynamic Programming (DP)을 사용하여 해결할 수 있는 문제입니다. 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)를 찾는 문제입니다.

#발상
주어진 수열 A에서, 각 위치에서 그 위치를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 찾아보자는 것이 발상의 기본입니다. 이렇게 각 위치마다의 LIS 길이를 구하면, 그 중 최대값이 전체 수열 A의 LIS 길이가 됩니다.

#해설
초기화: D[i] 배열은 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 저장합니다. 초기에는 모든 원소의 값이 1입니다. 왜냐하면, 각 원소 자체만으로 길이 1의 증가하는 부분 수열을 이룰 수 있기 때문입니다.

DP 수행: i번째 원소에 대해, 0부터 i-1번째 원소까지 비교를 수행합니다. 만약 A[j] < A[i]이면, j번째 원소가 i번째 원소 앞에 올 수 있으므로, D[i] = max(D[i], D[j] + 1)를 수행합니다. 이는 i번째 원소 앞에 올 수 있는 j번째 원소들 중, 가장 긴 증가하는 부분 수열에 i번째 원소를 추가하는 것입니다.

결과 출력: D[i] 배열 중 가장 큰 값을 출력합니다. 이 값이 주어진 수열 A의 가장 긴 증가하는 부분 수열의 길이입니다.

#코드 설명
vector<int> A(1001)와 vector<int> D(1001,1)는 각각 수열 A와 각 위치의 LIS 길이를 저장합니다.
수열 A의 크기 N을 입력받고, N개의 원소를 A에 저장합니다.
이중 반복문을 통해 각 위치에서 LIS 길이를 계산합니다.
계산된 LIS 길이 중 최대값을 MAX 변수에 저장합니다.
MAX 값을 출력합니다.
이 방법을 통해, O(N^2)의 시간 복잡도로 문제를 해결할 수 있습니다.