12015번 가장 긴 증가하는 부분 수열

문제링크 : www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

유사문제 참고 링크 :

2021.03.15 - [Baekjoon Online Judge] - 11053번 가장 긴 부분수열

---

---

<알고리즘>

1) 가장 긴 부분 수열이 될 배열 sequence 생성

2) 처음 입력받은 숫자들의 배열 numbers를 처음부터 돌면서

   2-1) numbers[i]가 sequence의 마지막 값보다 큰 값이면 push_back

   2-2) 작은 값이면 lower_bound를 이용하여 numbers[i]보다 큰 수중 가장 작은 수 찾아 numbers[i]로 대체.

3) 그렇게 numbers를 다 돌고 만들어진 sequence의 길이를 return 

 

 

 

ex) 진행 과정 

input :  6      10 20 10 30 20 50

now status => sequence is empty && numbers = {10,20,10,30,20,50}

first step. i=0,

  sequence is empty. => sequence.push_back(numbers[i])

  (seqeunce = {10})

seconde step i=1,

  sequence.back()<numbers[i]  => sequence.push_back(numbers[i])

  (sequence = {10, 20})

thirde step i=2,

   sequence.back()>numbers[i] => iterator = lower_bound(sequence.begin, sequence.end, numbers[i])

                                             *iterator = numbers[i]

   (lower_bound = 0  => sequence = {10,20})

fourth step i=3,

  sequence.back()<numbers[i]  => sequence.push_back(numbers[i])

  (sequence = {10, 20, 30})

fifth step i=4,

  sequence.back()>numbers[i] => iterator = lower_bound(sequence.begin, sequence.end, numbers[i])

                                             *iterator = numbers[i]

   (lower_bound = 1  => sequence = {10, 20, 30})

sixth step i =5,

  sequence.back()<numbers[i]  => sequence.push_back(numbers[i])

  (sequence = {10, 20, 30, 40})

finally, sequence is {10,20,30,40} => sequence.size = 4

 

 

 

+) lower_bound에 대하여 간단한 정리

#include <algorithm> 필요

lower_bound(v.begin(), v.end(), numbers[i](비교의 기준이 될 숫자)) 

lower_bound 의 return 값 = 주어진 key(numbers[i])보다 큰 값들중 가장 작은 값의 위치(iterator 형식)

참고 : chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기

 

 

 

 

 

메모리 : 5904KB      시간 : 500ms

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

int main() {

	int N = 0;
	cin >> N;

	vector<int> numbers(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> numbers[i];
	}

	vector<int> sequence;
	for (int i = 0; i < N; i++) {
		if (sequence.empty() || sequence.back() < numbers[i]) {
			sequence.push_back(numbers[i]);
		}
		else {
			vector<int>::iterator iter = lower_bound(sequence.begin(), sequence.end(), numbers[i]);
			*iter = numbers[i];
		}
	}

	cout << sequence.size();
	return 0;
}