BOJ 2565 전깃줄

1 개요

BOJ 2565 전깃줄

• 백준 온라인 저지 2565번 문제
• BOJ 23단계

2 C++

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

int N;
typedef struct {
    int a;
    int b;
} Line;
Line A[100];
int B[100];

void solve() {
	sort(A, A+N, [](Line x, Line y) {
       return x.a < y.a;
    });
	for (int i=0; i<N; i++) {
	    B[i] = 1;
	}
	for (int i=1; i<N; i++) {
	    int MAX = 0;
		for (int j = 0; j < i; j++) {
			if (B[j] > MAX && A[j].b < A[i].b) {
			    MAX = B[j];
			}
		}
		B[i] = MAX + 1;
	}
	int MAX = 1;
	for (int i=0; i<N; i++) {
		if (MAX < B[i]) {
		    MAX = B[i];
		}
    }
	cout << N - MAX;
}

int main(void) {
	cin >> N;
	for (int i=0; i<N; i++) {
	    cin >> A[i].a >> A[i].b;
	}
	solve();
}