백준 2565번: 전깃줄

 

백준 2565번: 전깃줄

2565번: 전깃줄

 

나는 풀이가 고민도 안될정도로 아무것도 떠오르지 않을때는 바로 답지를 보는편이다. 처음에 생각해 본것은 전깃줄을 없애는 방법과 없애고나서 그것을 어떻게 이용하여 최솟값을 찾는지에 대한 고민을 해봤지만 아무것도 생각나지 않았다. LIS문제라는 힌트를 얻어도 어떻게해야할지 모르겠다. 그래서 결국엔 답을 봤다. 전깃줄을 없애는 것보다는 안겹치고 몇개까지 만들 수 있냐를 구하는 것이다. 입력을 어느 한쪽의 전봇대 기준으로 정렬을 했을 때, 나 같은경우는 전봇대 A를 정렬을해서 B의 순서보다 앞에있으면서 B 전깃줄 보다 작은 값을 가지고있는 숫자들을 찾도록하는 LIS 방식으로 문제를 해결했다.

전체 전봇대 - 만들 수 있는 경우 = 정답

 

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

int solution(vector<pair<int, int>> elec);

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

    //입력
    vector<pair<int, int>> elec;
    int number_of_elec;
    cin >> number_of_elec;
    for(int i = 0; i < number_of_elec; i++){
        int a, b;
        cin >> a >> b;
        elec.push_back({a, b});
    }

    //풀이
    int answer = solution(elec);
    cout << answer;
    return 0;
}

int solution(vector<pair<int, int>> elec){
    int answer = 0;
    sort(elec.begin(), elec.end());
    vector<int> dp;
    int len = elec.size();
    //dp 초기화
    for(int i = 0; i < len; i++){
        dp.push_back(0);
    }
    
    // LIS
    for(int i = 0; i < len; i++){
        int m = 0;
        for(int j = 0; j < i; j++){
            if(elec[i].second > elec[j].second){
                m = max(dp[j], m);
            }
        }
        dp[i] = m + 1;
    }
    for(auto d : dp){
        answer = max(answer, d);
    }
    answer = len - answer;
    return answer;
}