Baekjoon Review
[Gold 2] 12015 가장 긴 증가하는 부분 수열
hanseongbugi
2024. 9. 23. 22:16
https://www.acmicpc.net/problem/12015
이 문제는 이진 탐색 알고리즘을 사용하여 해결하였다.
이진 탐색을 사용해야하는 이유는 N의 최대가 1000000이므로
DP를 사용 시 2중 반복을 사용해야하기 때문에 10^12가 되므로 1초를 초과하게 된다.
따라서 이진 탐색을 사용해 부분 수열의 길이를 구해야한다.
초기 A[0]를 result 배열에 삽입한다.
이후 1부터 N까지 반복을 진행한다.
result 배열에 최근에 넣은 값과 A[i]와의 값 비교를 통해
A[i]가 더 큰 경우 부분 수열의 후보군에 해당하므로 result 배열에 삽입한다.
하지만 A[i]가 작거나 같은 경우 이진 탐색을 통해 A[i]가 들어갈 위치를 찾게된다.
아래는 알고리즘을 구할 때 도움이 된 블로그 글이다.
BOJ - 12015 가장 긴 증가하는 부분 수열 2 해결 전략 (C++)
문제 링크백준 12015번 - 가장 긴 증가하는 부분 수열 2 본 문제는 BOJ에서 상당히 유명한 문제 유형인 LIS(Longest Increasing Sequence)의 두 번째 문제이다. 기본 LIS 문제들은 두 가지 타입으로 풀이법이
velog.io
#include <iostream>
#include <vector>
using namespace std;
int N;
int A[1000000];
int answer;
vector<int> result;
int binary(int key){
int st = 0, en = result.size() - 1;
while(st < en){
int mid = (st + en) / 2;
if(key > result[mid])
st = mid + 1;
else
en = mid;
}
return en;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>N;
for(int i = 0;i<N;i++)
cin>>A[i];
result.push_back(A[0]);
answer = 1;
for(int i = 1;i<N;i++){
if(result.back() < A[i]){
result.push_back(A[i]);
answer++;
}
else{
int idx = binary(A[i]);
result[idx] = A[i];
}
}
cout<<answer;
}