[백준] 오름세 (3745번)

문제

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

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

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

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

입력

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. 주가는 한 개 이상의 공백으로 구분되어 있으며, 그 외의 위치에서도 자유롭게 나올 수 있다. 주가는 100,000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 주가의 가장 긴 오름세의 길이를 출력한다.

예제 입력 1 복사

6 5 2 1 4 5 3 3 1 1 1 4 4 3 2 1

예제 출력 1 복사

3 1 1

---

최장 증가수열 문제이다.

dp를 이용해서 풀었는데 O(n^2) 이라서 시간초과가 떴다.

O(NlogN)의 풀이로 풀어야 한다.

 

lower_bound를 이용한 벡터 풀이로 바꿔서 해결했다.

lis라는 벡터에 최장 증가 수열을 저장하면서 각 인덱스에 넣을 수 있는 가장 작은 값만 기록하는 풀이이다. 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%98%A4%EB%A6%84%EC%84%B8%20(3745%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int N;
vector<int> lis;

int main()
{
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	while (cin>>N) {
		lis.clear();
		for (int cur, i = 1; i <= N; i++) {
			cin >> cur;
			if (lis.empty() || lis.back() < cur) lis.push_back(cur);
			else {
				int idx = lower_bound(lis.begin(), lis.end(), cur) - lis.begin();
				lis[idx] = cur;
			}
		}
		cout << lis.size() << "\n";
	}
}