[C++] 백준 2565: 전깃줄

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

 

풀이

입력을 받을 때 두 개의 전깃줄을 동시에 받으므로 vector 자료형의 pair를 통해 받은 뒤,

정렬을 해주면 될 것 같았다.

 

 

정렬을 하고 ,

dp[i] = i번째 전깃줄이 교차하지 않고 연결되어 있기위한 없애야 하는 전깃줄의 최소 개수

로 가정하고 풀이를 떠올려봤는데 도저히 감이 안 잡혔다.

 

 

인터넷 검색을 통해 풀이를 슬쩍 봤는데,

가장 긴 증가하는 부분수열을 활용하는 문제라고 나와있었다.

그걸 보자마자 무릎을 탁 쳤다!!

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

 

 

dp[i] = i번째까지 중 가장 긴 증가하는 부분수열의 길이로 하면

이미 좌측 배열의 값은 정렬이 되어있는 상태이기에, dp[i] = i번째까지의 전깃줄 중 교차하지 않고 연결된 전깃줄의 최대 개수가 되는 것이다!!

 

 

그럼 처음에 입력받은 n에서 dp배열의 최댓값을 빼면 바로 답이된다.

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int dp[105];
vector <pair<int, int>> v;

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

    int n;
    cin>>n;
    for(int i = 0; i < n; i++){
        int tmp1, tmp2;
        cin>>tmp1>>tmp2;
        v.push_back({tmp1, tmp2});

        dp[i] = 1;
    }

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

    for(int i = 1; i < n; i++){
        for(int j = 0; j < i; j++){
            if(dp[i] == dp[j] && v[i].second > v[j].second) dp[i]++;
        }
    }

    int myMax = -1;
    for(int i = 0; i < n; i++){
        myMax = max(myMax, dp[i]);
    }
    cout<<n-myMax;
    return 0;
}

 

dp 배열의 값을 꼭 문제에서 출력하는 것과 동일하게 할 필요는 없다는 걸 깨닫게 해준 문제이다!