[백준/C,C++] 2565번: 전깃줄

www.acmicpc.net/problem/2565

2565번: 전깃줄

hackids.tistory.com/26

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

언뜻 보면 잘 모를 수 있지만, 자세히 보면 11503번: 가장 긴 증가하는 부분 수열 문제와 상당히 유사합니다. 연결된 전깃줄은 계속 번호가 증가해야 서로 교차되지 않습니다. 어느 쪽이 됐던 양쪽 중 한쪽의 전깃줄을 오름차순으로 정렬하고 반대쪽의 전깃줄 중에 가장 긴 증가하는 부분 수열을 찾으면 됩니다.

예제입력	1	3	2	4	6	10	9	7
	8	9	2	1	4	10	7	6
A기준 정렬	1	2	3	4	6	7	9	10
	8	2	9	1	4	6	7	10
B기준 정렬	4	2	6	7	9	1	3	10
	1	2	4	6	7	8	9	10

A 기준 정렬 시, B 전봇대의 수열 중 가장 긴 증가하는 부분 수열은 1, 4, 6, 7, 10으로 길이가 5입니다. 가장 긴 증가하는 부분 수열을 찾고 그 외의 전깃줄을 끊어주면 교차하지 않는 형태가 됩니다. 8, 2, 9가 여기에 해당됩니다. B 기준 정렬 시를 보면, A 전봇대의 수열 중 가장 긴 증가하는 부분 수열은 2, 6, 7, 9, 10인데, 마찬가지로 길이가 5입니다. 끊어줘야 하는 전깃줄은 4, 1, 3입니다.

원래 예제 입력으로 주어진 전봇대와 전깃줄의 그림입니다.

 

A 기준 정렬 시, B 전봇대의 수열 중 가장 긴 증가하는 부분 수열에 해당하는 전깃줄 외 모두 제거한 그림입니다. 8, 2, 9번을 제거하면 모든 전깃줄이 교차하지 않습니다.

반대의 경우도 마찬가지입니다. 4, 1, 3번을 제거해도 모든 전깃줄이 교차하지 않습니다. 이제 이렇게 로직대로만 코드를 짜주면 됩니다.

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

using namespace std;

#define MAX 101

pair<int, int> input[MAX];
int DP[MAX];

bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first < b.first;
}

int main(void)
{
    int N; cin >> N;
    
    for (int i = 1; i <= N; i++) {
        cin >> input[i].first >> input[i].second;
    }
    
    sort(input + 1, input + 1 + N, cmp);

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < i; j++) {
            if (input[i].second > input[j].second) {
                DP[i] = max(DP[i], DP[j] + 1);
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        cout << DP[i] << " ";
    }

    int res = 0;
    for (int i = 1; i <= N; i++) {
        if (DP[i] > res) {
            res = DP[i];
        }
    }

    cout << N - res;

    return 0;
}