11568 풀이
※ 문제 링크 : https://www.acmicpc.net/problem/11568
이 문제는 동적 프로그래밍 문제의 하나로 Longest Common Subsequence와 유사성을 가지는 Longest Increasing Subsequence(이하 LIS)를 사용하는 문제입니다. 이런 LIS의 일반적인 구현은 아래와 같습니다.
input = [ 1, 2, 4, 5, 3] # [ ... ]에는 임의의 수열이 들어 갑니다.
n = len(input)
list = []
for i in xrange(0, n): # 1 ~ n
list.append(1)
for j in xrange(1, i): # 1 ~ i - 1
if input[i] >= input[j]:
list[i] = max([list[i], 1 + list[j]])
print max(list) # 3이 나오게 됩니다.
이것의 시간 복잡도는 \(O(n^2)\)이 됩니다. 하지만 이 시간 복잡도는 매우 느리므로 binary search를 활용해서 만들면 결과적으로 \(O(n\log n)\)의 시간 복잡도를 가진 알고리즘이 만들어지고, 결과적으로 아래와 같은 방식으로 문제를 풀 수 있습니다.
#include<iostream>
#include<algorithm>
#include<vector>
#include<limits>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
int num_of_card; // 카드의 수를 측정합니다.
int result = 0;
vector<int> seq;
seq.push_back(numeric_limits<int>::min()); // 이는 음수 무한대의 표현입니다.
cin >> num_of_card;
for(int i = 0; i < num_of_card; i++){ // LIS 알고리즘에 해당하는 부분입니다.
int value = 0;
cin >> value;
if(seq.back() < value){
seq.push_back(value);
result++;
}
else{ // 이 부분이 binary search를 하는 부분입니다.
auto it = lower_bound(seq.begin(), seq.end(), value);
*it = value;
}
}
cout << result;
return 0;
}