반응형
문제
수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제 입력 1
6
10 20 10 30 20 50
예제 출력 1
4
8
10 20 30 5 10 20 30 40
정답: 5
반례 추가
10
4 7 10 3 1 8 7 2 5 7
Answer: 4
7
7 9 10 8 2 3 7
Answer: 3
10
7 10 8 10 1 2 9 9 1 10
Answer: 4
9
2 8 3 10 5 1 5 2 3
Answer: 3
10
10 6 5 9 10 9 3 4 7 1
Answer: 3
10
5 8 10 3 9 1 5 8 5 6
Answer: 3
9
3 2 8 2 10 1 2 2 3
Answer: 3
10
3 8 10 1 5 7 9 8 9 6
Answer: 5
7
4 3 4 9 1 3 7
Answer: 3
10
8 6 8 9 5 1 4 4 6 3
Answer: 3
/*[12015]가장 긴 증가하는 부분 수열2*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN ((int)1e6+10)
int N;
int A[MAXN];
vector<int> v;
auto it = v.begin();
void InputData(){
cin >> N;
for(int i=0; i<N; i++){
cin >> A[i];
}
}
void Solve(){
v.push_back(A[0]);
for(int i=1; i<N; i++){
if(v.back() < A[i] ) v.push_back(A[i]);
else {
it = v.begin();
it = lower_bound(v.begin(), v.end(), A[i]);
*it = A[i];
}
}
cout << v.size() << endl;
}
int main(){
InputData();
Solve();
return 0;
}
/*[12015]가장 긴 증가하는 부분 수열2*/반응형
'Algorithm > 이분탐색' 카테고리의 다른 글
| [c++][algorithm][baekjoon]1300번 K번째 수 (0) | 2021.12.09 |
|---|---|
| [c++][algorithm][baekjoon]2110번 공유기 설치 (0) | 2021.12.09 |
| [c++][algorithm][baekjoon]2805 나무자르기 (0) | 2021.12.09 |
| [c++][algorithm]baekjoon 10816 숫자 카드2 (0) | 2021.07.06 |
| [c++][algorithm][baekjoon]1920 수 찾기 (0) | 2021.07.06 |
