[BOJ 3745] 오름세

- 문제 요약

 

주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다.

정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다.

n일 동안의 주가를 p1, p2, ..., pn이라고 했을 때, 오름세란 부분수열 pi1 < pi2 < ... < pik (i1 < i2 < ... ik)을 말한다.

n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

평범한 LIS 문제입니다.

테스트 케이스를 반복하며 구해주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

int n;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	while(cin>>n){
		vector<int>v;
		while(n--){
			int a;
			cin>>a;
			int w=lower_bound(v.begin(),v.end(),a)-v.begin();
			if(w==v.size()){
				v.push_back(a);
			}
			else if(v[w]>a){
				v[w]=a;
			}
		}
		cout<<v.size()<<"\n";
	}
}

코드 제출 결과