[백준 2352 - C++] 반도체 설계 : 이분 탐색

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

2352번: 반도체 설계

문제

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

 

입력

첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

 

출력

첫째 줄에 최대 연결 개수를 출력한다.

 

예제 입력 1 

6

4 2 6 3 1 5

예제 출력 1 

3

 

풀이

이 문제는 포트번호가 오름차순으로 될 수 있는 최장 길이를 구하는 것이다.

이를 구현하는 데에는 이분탐색을 함께 사용해서 시간 복잡도를 줄여야 한다.

입력을 받으면서 벡터에 있는 마지막 값보다 입력 값이 큰 경우에는 그냥 백터의 맨 뒤에 넣어주면 된다.

중요한것은 크지 않을 때이다.

이땐 이분탐색을 하여 이 입력 값 이상이 되는 위치 중 최소 인덱스를 찾아서 그 위치에 있는 값을 새로 입력 받은 값으로 갱신한다.

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector<int> result;

void insert(int port){
    int low = 0;
    int high = result.size()-1;
    int mid;
    
    while(high >= low){
        mid = (high + low)/2;
        if(result[mid] < port)
            low = mid + 1;
        else
            high = mid-1;
    }
    
    result[low] = port;
    
}

int main (void){
    int n, port;
    int idx=0;
    
    scanf("%d", &n);
    
    scanf("%d", &port);
    result.push_back(port);
    
    for(int i=1; i<n; i++){
        scanf("%d", &port);
        
        if(port > result[idx]){
            result.push_back(port);
            idx++;
        }
        else{
            insert(port);
        }
    }
    printf("%d\n", result.size());
}