[백준][dp] 2565 전깃줄 c++ 구현

목차

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

문제

 

문제 구현 방향

생각보다 아이디어가 잘 떠오르지 않는다. 나도 처음에는 막혀서 답을 보아버렸다..

아이디어는 총 세개이다.

 

1. 오른쪽 기준으로 정렬하기 -> 경우를 더 줄어야 한다.

2. 전깃줄을 교차하지 않기 위한 전깃줄의 최대 개수 구하기로 바꾸어 생각하기

 

-> 이렇게 생각하면 아래와 같은 문제로 변한다.

 

3. 증가하는 가장 긴 부분수열 구하기 

 

참고

https://be-senior-developer.tistory.com/23

[백준][dp] 11053 가장 긴 증가하는 부분 수열 c++ 구현

위에 문제를 풀어보았음에도 오래되어 생각이 잘 나지 않았다. 위의 문제를 풀어보면 더 쉽게 접근 할 수 있다.

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>


using namespace std;
int N, a, b;

vector<pair<int, int>>v;
int arr[502] = { 0 };
int dp[502] = { 0 };
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        v.push_back({ b, a });
    }
    sort(v.begin(), v.end());
    dp[0] = 1;
    for (int i = 0; i < v.size(); i++) {
        int prev = 0;
        for (int j = 0; j <i; j++) {
            if (i == 0)continue;
            if(v[i].second >= v[j].second){
                prev = max(dp[j], prev);
            }
        }
        dp[i] = prev + 1;
    }
    cout << N - *max_element(dp, dp+502);

    return 0;
}