[BOJ/Gold 2] 백준 12738 가장 긴 증가하는 부분 수열 3(C++)

문제 링크

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

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

 

알고리즘 분류

• 다이나믹 프로그래밍
• 이분 탐색

 

풀이

가장 긴 증가하는 부분 수열이 비어있거나, 수열의 마지막 수가 현재 A보다 작으면 A를 수열의 마지막에 추가한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, A;
vector<int> Vec;

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A;
		A += MAX;
		if (Vec.empty()) {
			Vec.push_back(A);
		}
		else {
			if (Vec.back() > A) {
				int Index = lower_bound(Vec.begin(), Vec.end(), A) - Vec.begin();
				Vec[Index] = A;
			}
			else if (Vec.back() < A) {
				Vec.push_back(A);
			}
		}
	}
}

void printAnswer() {
	cout << (int)Vec.size() << "\n";
}

int main() {
    FASTIO

	input();
    printAnswer();

    return 0;
}