BOJ 2565 - 전깃줄 링크
(2023.04.12 기준 G5)

문제

두 전봇대 A와 B 사이에 전깃줄이 N개가 있다. 그리고 전봇대에 연결되는 한 위치에 두 개 이상의 전깃줄이 연결되지 않는다. 이 때, 전깃줄이 교차하지 않도록 제거해야 하는 전깃줄의 최소 개수 출력

알고리즘

O(N^2) LIS DP. 이유는 풀이에서

풀이

전깃줄이 꼬이는 경우는? 두 전깃줄의 A의 대소 관계와 B의 대소 관계가 다른 것이다.
예제를 살펴보자.
1-8, 2-2 전깃줄을 살펴보면 1 < 2, 8 > 2. 대소 관계가 다르니 전깃줄이 꼬이게 되는 것이다.
역으로 말하면? 대소 관계가 같으면 꼬이지 않는다.

이는 전깃줄이 최대한 꼬이지 않는 관계를. 즉, 대소 관계가 같은 제일 긴 부분 전깃줄. 즉..! A의 위치를 기준으로 오름차순으로 정렬 후, B의 위치가 오름차순이 되는 전깃줄들의 제일 큰 집합을 찾아 그 집합을 제외하고 전부 제거하면 된다는 뜻이다.

A를 기준으로 예제를 정렬해보자.
B는 [8, 2, 9, 1, 4, 6, 7, 10] 으로 정렬이 된다.
여기서 그냥 가장 긴 증가하는 부분 수열을 찾으면 되는 것이다.

N이 최대 100이므로 O(N^2) LIS로도 충분하다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    vector<pii> pos;
    for (int i = 0, A, B; i < N; i++){
        cin >> A >> B;
        pos.push_back({A, B});
    }
    sort(pos.begin(), pos.end()); // A의 위치를 기준으로 정렬

    // LIS (O(N^2))
    vector<int> dp(N, 1);
    for (int i = 1; i < N; i++) for (int j = 0; j < i; j++)
        if (pos[j].second < pos[i].second) // B의 위치도 오름차순이면 두 전깃줄은 겹치지 않는 위치에 있다.
            dp[i] = max(dp[i], dp[j] + 1);

    // 찾은 가장 긴 증가하는 부분 전깃줄(수열)의 개수를 제외하고 전부 제거해야 한다.
    cout << N - *max_element(dp.begin(), dp.end());
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
pos = sorted(list(map(int, input().split())) for _ in range(N)) # A의 위치를 기준으로 정렬

# LIS (O(N^2))
dp = [1] * N
for i in range(1, N):
    for j in range(i):
        if pos[j][1] < pos[i][1]: # B의 위치도 오름차순이면 두 전깃줄은 겹치지 않는 위치에 있다.
            dp[i] = max(dp[i], dp[j] + 1)

# 찾은 가장 긴 증가하는 부분 전깃줄(수열)의 개수를 제외하고 전부 제거해야 한다.
print(N - max(dp))

여담

조만간 O(NlgN) LIS 문제를 다뤄보겠다.