JXNVCE ALGO-LOG YouJin Jung

BOJ-2565

04 Aug 2021

도무지 왜 LIS를 쓰는지 모르겠어서 질문 게시판이랑 구글링을 참고해서 풀었다… 사람들이 왜 DP 어렵다는지도 알겠고 와 어떻게 문제를 이렇게 나랑 딴판으로 해석하는지 신기하다

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

using namespace std;

// vector<pair<int, int>> sort(vector<pair<int, int>> p) {
//     int small, temp, temp2, i, j;
//     int n = p.size();
//     for (i=0; i<n-1; i++) {
//         small = i;
//     }
//     for (j=i+1; j<n; j++) {
//         if (p.at(j).first <= p.at(small).first) small = j;
//     }
//     temp = p.at(i).first;
//     temp2 = p.at(i).second;
//     p.at(i).first = p.at(small).first;
//     p.at(i).second = p.at(small).second;
//     p.at(small).first = temp;
//     p.at(small).second = temp2;
//     return p;
// }

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
    
    int T;
    cin >> T;
    vector<pair<int, int>> p;
    if (T>100) return 0;
    for (int i=0; i<T; i++) {
        int a, b;
        cin >> a >> b;
        if (a<500 && b<500) {
            pair <int, int> t;
            t.first = a;
            t.second = b;
            p.push_back(t);
        }
    }
    sort(p.begin(), p.end());
    for (auto i: p) {
        cout << i.first << " " << i.second << endl;
    }
    // vector<pair<int, int>> q = sort(p);
    // for (auto i: q) {
    //     cout << i.first << " " << i.second << endl;
    // }
    int dp[102], result;
    for (int i=1; i<=T; i++) {
        for (int j=0; j<i; j++) {
            if(p[i].second > p[j].second && dp[j]>=dp[i]) dp[i] = dp[j]+1;
        }
        result = max(result, dp[i]);
    }
    cout << T-result << endl;
    return 0;

}

Related posts