(C++) - 백준(BOJ) 3745번 : 오름세

 

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

3745번: 오름세

LIS문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. vector d를 선언합니다. 2. n을 EOF가 아닌동안 입력받습니다.  3. d를 n만큼 resize 합니다. n개의 방을 저장할 수 있게 됩니다.

 

📔 풀이과정

 n개의 수를 입력받을 때 마다 답을 저장할 vector인 d변수에 대해 d.begin부터 lis의 길이인 length까지의 범위에서 입력 받은 수를 key로 하여 lower_bound를 수행합니다. 값을 찾아 찾았다면 그 부분을 입력받은 값으로 치환하고 찾지 못했을 경우에는 더 긴 증가수열을 찾았기 때문에 length를 더해줍니다. 

 

📔 정답출력

LIS값 length를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> d;
int main(){
    while(cin >> n){
        d.resize(n,0);
        int length = 0;
        for (int i = 0; i < n; i++){
            int value;
            cin >> value;
            auto p = lower_bound(d.begin(), d.begin() + length, value);
            *p = value;
            if (p == d.begin() + length) length++;
        }
        cout << length << "\n";
    }
}