[백준 3745] 오름세 (C++)

문제 링크: www.acmicpc.net/problem/3745

3745번: 오름세

1. 주의할 점

- 이분탐색을 사용하는 LIS 알고리즘에 대해 알고 있어야 한다

- DP[] 배열을 TC마다 초기화한다

 

2. 구현

- 입력 받는 수들을 Arr[] 배열에 저장하면서 DP[] 배열을 전부 0으로 초기화한다

- DP[0] = Arr[0]과 idx=0을 초기화한다

- i: 1~Num-1까지 Arr[]에 있는 모든 수들에 대해 Arr[i]의 값이 DP[idx]보다 크다면 DP[++idx] = Arr[i]를 수행한다. 반대인 경우, 이분탐색을 통해 DP[]의 값을 갱신한다

(단, 아래의 코드는 LIS에 해당되는 값들이 DP[] 배열에 담기지 않는다)

#include <iostream>
using namespace std;
int arr[100000];
int dp[100000];

int b_search(int r, int v){
    int l=0,mid,result=r;
    while(l<=r){
        mid = l+(r-l)/2;
        if(dp[mid]>=v){
            result = mid;
            r = mid-1;
        }
        else
            l = mid+1;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num;
    while(1){
        if(cin>>num){
            for(int i=0;i<num;i++){
                cin>>arr[i];
                dp[i]=0;
            }
            dp[0]=arr[0];
            int idx=0;
            for(int i=1;i<num;i++){
                if(arr[i]>dp[idx])
                    dp[++idx] = arr[i];
                else{
                    int cidx = b_search(idx,arr[i]);
                    dp[cidx]=arr[i];
                }
            }
            cout<<idx+1<<'\n';
        }
        else break;
    }
    return 0;
}