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

www.acmicpc.net/problem/12015

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

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

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

 

---

 

⊙ 문제 접근 과정

 

LIS 문제이다. 시간 복잡도 O(N log N)으로 풀었다.

LIS가 무엇인지, O(N^2)의 풀이법을 보고 싶다면 tooo1.tistory.com/121

 

1. 크기 값을 입력 받는다.
2. 벡터 값을 입력받는데 조건문을 활용하여 입력받는다.

O(N log N)으로 풀 수 있게 한 주인공은 바로 Lower bound

 

Lower bound가 뭔지 궁금하다면? tooo1.tistory.com/126

 

---

 

⊙ 문제 풀이

 

#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

 

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