[BOJ] 11053. 가장 긴 증가하는 부분 수열 (dp, binary_search)

Silver II

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

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

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

input:

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
• 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

output:

• 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

---

Idea :

https://hio9105.tistory.com/entry/Algo-LIS-%EC%B5%9C%EC%9E%A5-%EC%A6%9D%EA%B0%80-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4

[Algo] LIS (최장 증가 부분 수열)

 

Code :   

#include <iostream>
#include <vector>

using namespace std;

/* lower_bound: 주어진 vector에서 x보다 크거나 같은 값의 위치를 구하는 함수 */
vector<int>::iterator lower_bound(vector<int> &LIS, int x) {
	for (auto it=LIS.begin(); it < LIS.end(); it++) {
		if (*it >= x) return it;
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	int N, input;
	vector<int> LIS;
	LIS.push_back(0); // back()으로 빈 벡터 배열 접근 방지를 위함

	cin >> N;
	for (int i=1; i<=N; i++) {
		cin >> input;
		if (input > LIS.back()) 
			LIS.push_back(input);
		else 
			*(lower_bound(LIS, input)) = input;
	}

	cout << LIS.size()-1 << "\n";
}

 

---

Result : 

메모리: 2020 KB,  시간: 0 ms

 

Review :