LCS(longest common subsequence)

http://www.acmicpc.net/problem/1965 상자넣기 문제인데 LCS문제임

기본적인 방법은 dp로 해결 할 수 있겠다

#include #include using namespace std; int N; int A[1005]; int d[1005]; int main(void){ // freopen("input.txt", "r", stdin); scanf("%d", &N); for(int i=0; i<N; i++) scanf("%d", &A[i]); for(int i=0; i<N; i++) d[i] = 1; for(int i=0; i<N; i++) for(int j=0; j<i; j++) if( A[j] < A[i] ) d[i] = max(d[i], d[j]+1); int ans = 0; for(int i=0; i<N; i++) ans = max(ans, d[i]); printf("%d\n", ans); return 0; } 약간 쉬운 다이나믹이긴한데 O(n^2)이라 n이 커지면 시간이 오래 걸릴거 같다 그래서 두번째로 더 좋은 방법은 lower_bound를 쓰는 것이다 #include #include #include using namespace std; int N; int a[1005]; int LIS[1005]; int main(void){ // freopen("input.txt", "r", stdin); scanf("%d", &N); for(int i=0; i<N; i++) scanf("%d", &a[i]); fill(LIS, LIS+N, 999999999); for(int i=0; i<N; i++) *lower_bound(LIS, LIS+N, a[i]) = a[i]; printf("%d\n", (int)(lower_bound(LIS, LIS+N, 999999999)-LIS)); return 0; } 코드도 더 간결하고 lower_bound는 binary search를 사용하기 때문에

이 코드의 시간복잡도는 O(nlogn)이 된다

채점할때도 시간차가 좀 느껴지는것 같다

근데 중요한것 이 방법을 이용하면 LIS의 길이만 알뿐, 실제 들어가 있는 값은 상관없다는것이다