BOJ 3745 - 오름세

https://www.acmicpc.net/problem/3745

3745번: 오름세

가장 긴 증가하는 부분수열의 길이(LIS)를 출력하는 문제다.

 

dp로 O(n^2) 수행시간에 해결하는 것은 종만북에서 해본 기억이 있지만, 입력이 10^6이라서 시간 초과가 난다.

 

https://kks227.blog.me/220436273634?Redirect=Log&from=postView

[3745번] 오름세(★★★☆☆)

라이님의 포스팅으로 공부했다. 이건 생각해내는 알고리즘이 아니라 배워서 이해하고 외워 가져가는 문제라고 결론냈다.. 너무 어렵..

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	while (scanf("%d",&n)>0) {
		vector<int> last(1, 0);
		for (int i = 0, cur; i < n; ++i) {
			scanf("%d", &cur);
			if (last.back() < cur) last.push_back(cur);
			else *lower_bound(last.begin(), last.end(), cur) = cur;
		}
		printf("%d\n", last.size() - 1);
	}
}

학교 스터디에서 lower_bound 연습문제로 주셨는데, 이진탐색보단 그리디한 접근에 더 초점을 맞춰야 한다고 본다.

 

벡터를 채우는 과정을 보면

v.back()보다 cur이 크면 바로 넣어주고 작으면 lower_bound로 자리를 찾아서 넣어준다.

arr : 1 3 5 7 4 5 6

v :   1

      1 3 

      1 3 5

      1 3 5 7

      1 3 4 7  //5 자리에 4가 들어갔지만 여기까지 봤을 때 LIS는 여전히 1357이다.

      1 3 4 5  

      1 3 4 5 6

 

v.size()-1이 정답이 된다.