[백준 / BOJ] 12015번: 가장 긴 증가하는 부분 수열 2

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

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

 

 

---

 

 

문제

---

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

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

 

입력

---

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

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

 

출력

---

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

 

예제 입력

---

6
10 20 10 30 20 50

 

예제 출력

---

4

 

코드 

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	vector<int> v;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		v.push_back(t);
	}

	vector<int> res;
	res.push_back(v[0]);
	for (int i = 1; i < n; i++) {
		if (*(res.end() - 1) >= v[i]) {
			auto iter = lower_bound(res.begin(), res.end(), v[i]);
			*iter = v[i];
		}
		else res.push_back(v[i]);
	}
	cout << res.size();
	return 0;
}

 

 

 

---

 

 

감이 잡히지 않아서 다른 블로그 글을 참고했다(https://ferrante.tistory.com/54).

 

위 블로그에서 설명이 아주 잘 되어 있다. 간단하게 설명하자면, 입력 배열과 가장 긴 부분수열을 저장하는 배열이 필요하다. 입력 배열의 원소와 가장 긴 부분수열 배열을 비교한다. 가장 긴 부분수열 배열의 끝 원소가 입력 배열의 원소보다 크면, 가장 긴 부분수열 배열에서 입력 원소에 해당하는 lower_bound를 찾아 그 위치의 원소를 입력 배열의 해당 원소로 바꾼다. 가장 긴 부분수열 배열의 끝 원소가 입력 배열의 원소보다 작다면 별다른 작업 없이 입력 원소를 가장 긴 부분수열 배열에 push해준다. 이 과정을 거치고 나면 가장 긴 부분수열 배열이 완성된다.

 

알고나니 간단한 알고리즘이다. 입력 배열을 순회하는 데에 드는 시간복잡도는 O(n), lower_bound를 구하는데에 필요한 시간복잡도가 O(log(n))이므로 O(n*log(n))의 시간복잡도로 문제를 해결할 수 있다.