[1일 1알고] G5 2565 전깃줄

 

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

 

꼬여있는 전깃줄을 풀어야 하는 문제입니다.

먼저 입력이 뒤죽박죽 주어지기 때문에 문제를 쉽게 풀기 위해서 A 전봇대의 높이에 따라 정렬해보았습니다.

 

그러고 보니 가장 적게 전깃줄을 자르는 횟수 = 가장 많은 전깃줄을 연결하는 횟수

라는 생각이 들었고

 

A측 전봇대는 이미 정렬되었기 때문에 B에 대한 최장 증가 부분 수열(LIS)을 구하면 답이 나올 것이라고 생각했습니다.

---

코드

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pair<int, int>> v(N);

    for (int i = 0; i < N; ++i)
    {
        cin >> v[i].first >> v[i].second;
    }

    sort(v.begin(), v.end());

    vector<int> res(N, 1);
    for (int i = 1; i < N; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (v[j].second < v[i].second)
            {
                res[i] = max(res[i], res[j] + 1);
            }
        }
    }

    cout << N - *max_element(res.begin(), res.end());
    return 0;
}

 결론적으로 위와 같은 코드가 나왔습니다.

N이 작아 O(N^2)의 코드로 간단히 풀었지만 아니라면 O(NlogN)의 방법으로 해결하면 될 것으로 보입니다.