[3745] 오름세 C++

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

3745번: 오름세

- lower_bound 사용하기

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

int main() {

	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	int n;

	while (cin >> n) {
		vector<int> vec;

		for (int i = 0; i < n; i++) {
			int num;
			cin >> num;
			if (vec.empty() || vec.back() < num)
				vec.push_back(num);
			else {
				// vector에서 입력받은 값과 같거나 큰 수 중 가장 작은 수의 위치
				int tmp = lower_bound(vec.begin(), vec.end(), num) - vec.begin();
				vec[tmp] = num;
			}
		}

		cout << vec.size() << endl;
	}

	return 0;
}

 

- 시간초과

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

int main() {

	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	int n;

	while (cin >> n) {
		int arr[100001];
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}

		int MAX = 1;
		int len[100001] = { 0 };
		for (int i = 1; i < n; i++) {
			len[i] = 1;
			for (int j = i - 1; j >= 0; j--) {
				if (arr[i] > arr[j])
					len[i] = max(len[i], len[j] + 1);

				if (len[i] > MAX)
					MAX = len[i];
			}
		}

		cout << MAX << "\n";
	}

	return 0;
}