백준 No.12015 [가장 긴 증가하는 부분 수열 2]

Baekjoon Online Judge No.12015 [가장 긴 증가하는 부분 수열 2]

---

 문제 

12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net)

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

---

 설명 

2021.07.28 - [Algorithm (C++ based)/BOJ] - 백준 No.11053 [가장 긴 증가하는 부분 수열]

백준 No.11053 [가장 긴 증가하는 부분 수열]

 

  위 문제에서 배열의 크기와 숫자의 범위가 더 커졌다. 따라서, 위 [가장 긴 증가하는 부분 수열] 문제는 배열을 short type 으로 선언을 하였지만 이번 문제에선 int type 으로 자료형을 변경함으로써 풀 수 있다.

---

 Code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> arr;
vector<int> list;

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

	// arr를 입력 받는다.
	cin >> n;
	arr.assign(n + 1, 0);
	list.assign(1, -1111111);

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];

		if (list[list.size() - 1] < arr[i]) { // 현재 입력된 수가 지금 list에서의 가장 우측의 최대값보다 큰 경우
			list.push_back(arr[i]); // list 의 우측에 삽입한다.
		}
		else { // 그렇지 않은 경우
			   // 현재 숫자 크기 이상의 숫자가 나오는 list 에서의 index를 탐색
			int inputIndex = lower_bound(list.begin(), list.end(), arr[i]) - list.begin();
			list[inputIndex] = arr[i]; // 탐색한 index 에 현재의 수를 대입
		}
	}

	cout << list.size() - 1; // list[0]는 사용하지 않고 list[1] 이후로만 사용이 되므로
							 //   list 의 size 보다 1 작은 값을 출력
}