[백준(BOJ)] 12738번 : 가장 긴 증가하는 부분 수열 3 - C++[CPP]

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

12738번: 가장 긴 증가하는 부분 수열 3

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 이분 탐색
• 가장 긴 증가하는 부분 수열: O(n log n)

 

---

⊙ 문제 접근 과정

 

https://tooo1.tistory.com/131 코드와 문제 접근 과정 동일

 

---

⊙ 문제 풀이

 

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

using namespace std;

int a;
vector<int> arr;

int main() {
    cin >> a;

    for (int i = 0; i < a; i++) {
        int input;
        cin >> input;
        if (arr.empty() || arr.back() < input) {
            arr.push_back(input);
        } else {
            *lower_bound(arr.begin(), arr.end(), input) = input;
        }
    }
    cout << arr.size();
}

---

⊙ 결과

 

---

 

 

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!