당신이 무엇을 배우고 있다는것은 어제의 당신보다 훨씬 높은 가치가 되었다는 것이다

기본적인 방법은 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의 길이만 알뿐, 실제 들어가 있는 값은 상관없다는것이다

바이너리 서치하다가 위그림 같은 상황이 되었다고 하자

내가 지금 찾으려는 값보다 작으면 현재의 mid는 답이 아니라는 소리고

 left가 mid로 바뀌게 될 것이다

그리고 새로운 미드를 (left+right)/2;로 한다면

새로운 mid는 이전의 mid와 같은 값을 갖게되고, 그 이후로도 계속 left와 mid는 

같은값을 갖게되어 무한루프에 빠지게 된다

그래서 이런경우에는 left를 mid로 바꿔준후

이래 해주면 새로운 mid는 이전의 mid가 아닌 right로 새로운 값을 갖게 된다

그리고 그 mid가 내가 찾는 답이 될것이다