[BOJ] 백준 2565 전깃줄 (문제 설명, 코드, C++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 백준의 2565번 전깃줄 문제입니다.

 

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

 

 

 

 

 

해결 과정

 

 

예제 )

 

왼쪽 전봇대 기준 오름차순으로 정렬

 

LIS 문제 익숙하다면 가장 긴 증가하는 부분순열을 구하면 

이게 바로 전깃줄에 의해 방해받지 않는 전깃줄들의 집합이기에

 전체 전깃줄에서 빼주면 전깃줄들을 가로질러 방해하는 전깃줄들의 수를 구할 수 있습니다.

 

 

 

 

코드 전문

 

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

using pii = pair<int, int>;

int n;
vector<pii> line_arr;

int dp[502];

bool comp(pii a, pii b) {
    return a.first < b.first;
}

int main () {
    cin >> n;

    int t_l, t_r;
    for (int i = 0; i < n; ++i) {
        cin >> t_l >> t_r;
        pii t_p = {t_l, t_r};
        line_arr.emplace_back(t_p);

        dp[i] = 1;
    }

    sort(line_arr.begin(), line_arr.end(), comp);

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

    cout << n - mx_v;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

 

많이 풀어봐야 직관력이 늘 것 같습니다. 화이팅

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.