BOJ 2565번 : 전깃줄

전신주 사이에 전선이 겹치지 않게 하려면 A전신주의 번호가 증가 할 때, 각 번호에 연결된 B전신주의 번호가 계속 증가해야 한다.

 

A전신주의 1번을 보았을때, 1번은 8번과 연결 되있는데, 2번은 2와 연결 되어있으므로, 전깃줄이 교차하지만, 3번은 9번과 연결되어 겹치치 않는다. 이렇게 A 전신주 기준으로 각 번호에 연결된 B전신주의 번호가 증가하는 LIS를 찾는 문제이다.

 

또한, A전신주의 각 번호에 따라 LIS 가 작아지면 의미가 없기때문에 계속 큰 수를 업데이트 해야하기에 DP또한 사용된다.

 

위 설명을 표로 보면 아래와 같다.

최대 연결 개수는 같은 번호의 LIS 와 바로 전 최대 연결 개수의 최대값이다. 즉,

 

res[n] = max(res[n-1], LIS[n])

 

<소스코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX(X,Y) ((X)>(Y)?(X):(Y))
vector<int> res;
vector<int> LIS;
void find(vector<int> &temp, int target) { //끼어들 곳 찾는 함수
    int in = temp.size()-1;
    for (int i = in; i > 0; i--) {
        if (target <= temp[i])
            continue;
        else {
            temp[i + 1] = target;
            break;
        }
    }
    if (target < temp[0])
        temp[0] = target;
}
int LIS_find(vector<vector<int>>&arr, int start, int n ) { // LIS 계산함수
    vector<int> temp;
    temp.push_back(0);
    for (int j = start; j < n+1; j++) {
        if (arr[j-1][1] > temp.back())
            temp.push_back(arr[j-1][1]);
        else
            find(temp, arr[j-1][1]);
    }
    return temp.size()-1;
}
int main() {
    int n, tmp1, tmp2;
    vector<vector<int>> arr;
    cin >> n;
    for (int i = 0; i < n; i++) {
        vector<int> v(2);
        cin >> v[0] >> v[1];
        arr.push_back(v);
    }
    sort(arr.begin(), arr.end());
    res.push_back(0);
    for (int i = 1; i < n + 1; i++)
        res.push_back(MAX(LIS_find(arr, i, n), res[i - 1]));
    cout << n-res[n] << endl;
}

문제 : 

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

2565번: 전깃줄