[BOJ / C++] 2565번 : 전깃줄

문제

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, < 그림 1 >과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.

< 그림 1 >

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

Solved.ac 레벨

골드 V

풀이

골드 V에는 다이나믹 프로그래밍 문제가 많은 것 같다. 그냥 랜덤으로 고른 문제가 대체로 다이나믹 프로그래밍 문제군.

이 문제는 생각보다 어렵지 않았다. 

 

우선 문제에서 제시된 예제를 pair<int, int> 형태의 배열로 나타내면 (first를 A, second를 B로 하자)

A	1	3	2	4	6	10	9	7
B	8	9	2	1	4	10	7	6

예제 입력은 정렬이 되어있지 않은 상태라 이렇게 보면 어떤걸 지워야 하는지 감이 잡히지 않는다.

문제에 첨부된 그림처럼 A를 기준으로 오름차순으로 정렬을 해야 한다.

정렬된 상태의 배열은 아래와 같다.

A	1	2	3	4	6	7	9	10
B	8	2	9	1	4	6	7	10

문제에서는 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 된다고 했다. 이걸 지워보자.

A	1	2	3	4	6	7	9	10
B	8	2	9	1	4	6	7	10

문제에서 주어진 전깃줄들을 지우고 나면 남은 B의 위치는 2, 4, 6, 7, 10. 증가하는 부분 수열이다.

 

즉 이 문제는 주어진 B의 전깃줄의 위치로 가장 긴 증가하는 부분 수열을 찾는 문제다.

없애야 하는 전깃줄의 갯수는 (전체 전깃줄의 개수 - 가장 긴 증가하는 부분 수열) 과 같다.

 

가장 긴 증가하는 부분수열, 즉 LIS를 구하는 방법은

백준 11053번 : 가장 긴 증가하는 부분 수열 문제를 풀면서 알아본 적이 있다. 따라서 이에 대한 풀이는 전에 내가 올렸던 LIS 문제 풀이를 참고하면 된다.

11053번: 가장 긴 증가하는 부분 수열

[BOJ / C++] 11053번 : 가장 긴 증가하는 부분 수열

Code

#include<bits/stdc++.h>

using namespace std;

int n;
vector<int> dp(101);
vector<pair<int, int>> line;

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

    cin >> n;

    line.push_back({0, 0});

    for(int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        line.push_back({a, b});
    }

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

    for(int i = 1; i <= n; i++) {
        dp[i] = 1;
        for(int j = 1; j < i; j++) {
            if(line[i].second > line[j].second) {
                dp[i]= max(dp[i], dp[j] + 1);
            }
        }
    }

    cout << n - *max_element(dp.begin(), dp.end()) << "\n";

    return 0;
}

 

2565번: 전깃줄