문제 URL : www.acmicpc.net/problem/3745
3745번: 오름세
입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다.
www.acmicpc.net
문제접근법 :
주가의 가장 긴 오름세의 길이를 출력한다고 나와있기에
주어진 주가들 중에서 상한가가 될수있는 입력값들을 찾으면된다.
즉 최장증가수열인 LIS알고리즘 보통 LIS알고리즘은 O(N^2)이지만
이분탐색을 이용하면 O(nlogn)의 시간복잡도를 가진다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
//콩순이냉장고
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (cin>>n) {
vector<int> v(1,-1e+9);
for (int i = 0; i < n; i++)
{
int t;
cin >> t;
if (v.back() < t)
v.push_back(t);
else
{
auto it = lower_bound(v.begin(), v.end(), t);
*it = t;
}
}
cout << v.size() - 1 << "\n";
}
}
|
cs |
모르는점 혹은 궁금한점 언제든 질문 댓글은 환영입니다.
'백준' 카테고리의 다른 글
| 백준 14502 연구소 (0) | 2021.02.17 |
|---|---|
| 백준 2568 전깃줄 - 2 (0) | 2021.02.15 |
| 백준 9370 미확인 도착지 (0) | 2021.02.15 |
| 백준 16235 나무 재테크 (0) | 2021.02.15 |
| 백준 16920 확장 게임 (0) | 2021.02.15 |
