[백준] 2565 전깃줄

https://www.acmicpc.net/problem/2565

증가하는 가장긴 부분수열을 찾는 문제이다. 

#include <cstdio>
#include <algorithm>

using namespace std;
const int SIZE = 102;

int d[SIZE]; // 증가하는 부분수열 값 그 자체
pair<int, int> arr[SIZE];

int main() {
    int n; // eq-less 100
    scanf("%d", &n);
    for (int i = 0; i < n; ++i){
        scanf("%d %d", &(arr[i].first), &(arr[i].second));
    }
    sort(arr, arr+n);

    int idx = 0;
    int len = 0;
    d[0] = arr[0].second;
    for (int i = 1; i < n; ++i) {
        if (d[idx] < arr[i].second) {
            d[++idx] = arr[i].second;
        } else {
            int tmp = lower_bound(d, d+idx, arr[i].second) - d; // 들어갈자리를 찾아서 넣는다.
            d[tmp] = arr[i].second;
            ++len;
        }
    }

    printf("%d\n", len);
}

 

from bisect import bisect_left

def solve(n, arr):
    arr.sort(key=lambda x: x[0])

    d = []
    idx = 0
    length = 0
    d.append(arr[0])
    for i in range(1,n):
        if d[idx][1] < arr[i][1]:
            idx+=1
            d.insert(idx, arr[i])
        else:
            tmp = bisect_left([i[1] for i in d], arr[i][1], 0, idx)
            d[tmp] = arr[i]
            length += 1
    print(length)


if __name__ == "__main__":
    n = int(input())
    arr = [[int(j) for j in input().split()] for i in range(n)]

    solve(n, arr)