[백준] 2565번 : 전깃줄

문제

 

---

풀이

 

myunji.tistory.com/214

[백준] 11053번 : 가장 긴 증가하는 부분 수열

이 문제의 응용 문제이다.

 

교차하지 않는다는 의미가 무엇을까? A의 원소 i, j가 있다고 하고 이 i, j가 향하는 B의 위치를 A[i], A[j]라고 하자.

A의 모든 전깃줄에 대해 교차하지 않으려면

 

A에서 i<=j를 만족하는 모든 i와 j에 대해

A[i]<=A[j]를 만족해야 한다.

 

그냥 간단하게 말하면 증가 수열이여야 한단 것이다.

그니까 결국 input을 A기준으로 정렬한 뒤 11053번에서 사용한 코드를 적용하면 된다는 거다.

---

소스코드

 

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

struct elec { //source에서 나와서 dest로 들어가는 것
    int source, dest;
};
elec* elecs = new elec[101];
int dp[101] = { 0, };

bool cmp(const elec& e1, const elec& e2) { //source 기준으로 정렬
    if (e1.source < e2.source)
        return true;
    else
        return false;
}

int min_elec(int tot_line) {
    int point = 1; //최대 길이가 나옴
    dp[1] = elecs[1].dest;
    for (int i = 2; i <= tot_line; i++) {
        for (int j = point; j >= 0; j--) {
            if (elecs[i].dest > dp[j]) {
                dp[j + 1] = elecs[i].dest;
                if (j == point)
                    point++;
                break;
            }
        }
    }
    return tot_line - point; //전깃줄 수에서 최대 길이를 빼면 답이 나옴
}

int main() {
    int tot_line;

    cin >> tot_line;
    for (int i = 1; i <= tot_line; i++)
        cin >> elecs[i].source >> elecs[i].dest;
    sort(elecs + 1, elecs + tot_line + 1, cmp); //1부터 시작했으니까 1씩 더해줘야함
    cout << min_elec(tot_line);
}

정렬을 제외하고는 11053번과 거의 유사하니 굳이 설명하지 않겠다.