[백준]2565-전깃줄(설명X, Dynamic Programming)

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;
 
int countLine(int N);
 
class Line {
private:
    int A, B;
public:
    void setLine(int A, int B) {
        this->A = A;
        this->B = B;
    }
    bool operator<(Line line) {
        if (this->A < line.A)
            return true;
        return false;
    }
    int getB() {
        return this->B;
    }
};
 
int main() {
    int N;
    scanf("%d", &N);
    printf("%d\n", countLine(N));
}
 
int countLine(int N) {
    int* ary = new int[N] {0, };
    Line* line = new Line[N];
    for (int i = 0; i < N; i++) {
        int A, B;
        scanf("%d %d", &A, &B);
        line[i].setLine(A, B);
    }
    sort(line, &line[N]);
 
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            if (line[i].getB() < line[j].getB() && ary[i] == ary[j])
                ary[j]++;
    int max = 0;
    for (int i = 0; i < N; i++)
        if (max < ary[i])
            max = ary[i];
 
    delete[] line;
    delete[] ary;
    return N - (max + 1);
}