풀이
lower bound를 써주자!
더 큰 상자가 최소 어디에 들어갈 수 있는지 lower bound로 찾으면 된다!
O(n^2) dp대신에 lower bound를 써주면 O(nlogn)에 풀 수 있따!
코드
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, len, a[1001];
int main() {
scanf("%d", &n);
while (n--) {
int tmp;
scanf("%d", &tmp);
auto it = lower_bound(a, a + len, tmp);
if (*it == 0) len++;
*it = tmp;
}
printf("%d", len);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge