(c++) LIS BOJ 2565번: 전깃줄

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

2565번: 전깃줄

 

---

 

 

문제 개요

 

 

문제만 보면 LIS를 어떻게 이용할지 감이 안 잡히는데

 

겹친다는 개념을 생각해보면 답이 나온다.

 

전봇대는 오름차순 순서대로 두 개가 세워져있고, 그 사이 전깃줄이 있는 형태이다.

 

전깃줄이 겹치려면 아래의 경우를 만족해야 한다.

 

왼쪽에 있는 숫자가 작은 것이 연결되어있는 오른쪽 숫자가 더 클 경우

ex) 1 - 4, 2 - 1 겹침

 

왼쪽 전봇대가 정렬되있는 순서대로 오른쪽 전봇대에 연결된 숫자를 차례로 나열해보면

 

겹치는 전깃줄이 없는 최대의 경우는 나열된 숫자가 커지는 LIS를 찾으면 되는 것이다. 

 

예시로 입력이 아래와 같이 주어진다면

4

3 1

2 3

1 2

4 4

 

왼쪽을 기준으로 오름차순 정렬하여 연결된 오른쪽 전봇대에 연결된 숫자를 나열하면

2 3 1 4 → LIS는 2 3 4 인 3이다.

겹치지 않고 최대로 연결할 수 있는 수가 3이라는 뜻이 된다.

 

그럼 주어진 전체 전깃줄 개수인 4에서 3을 빼면 정답인 1이 나오게 된다.

 

 

코드

 

 

#include <bits/stdc++.h>

using namespace std;

int n;
vector<pair<int, int> > AB;
int right_e[101];
int cache[101];

int lis(int start) {
    int& ret = cache[start];
    if (ret != -1) return ret;
    ret = 1;
    for (int next = start+1; next < n; next++) {
        if (right_e[start] < right_e[next]) {
            ret = max(ret, lis(next) + 1);
        }
    }
    return ret;
}

int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        AB.push_back({a, b});
    }
    sort(AB.begin(), AB.end());
    for (int i = 0; i < n; i++) {
        right_e[i] = AB[i].second;
    }
    fill_n(cache, 101, -1);
    for (int i = 0; i < n; i++) {
        lis(i);
    }
    int max_lis = 0;
    for (int i = 0; i < n; i++) {
        max_lis = max(max_lis, cache[i]);
    }
    cout << n - max_lis;
}