전깃줄

문제

나의 풀이

처음 이 문제는 그리디 문제라고 생각했다.
즉 많이 겹치는 부분을 먼저 삭제하고 더 이상 겹치는 부분이 없을 때까지 진행하였다.

쉽게 말해
1 - 8 => 5겹침
2 - 2 => 2겹침
3 - 9 => 4겹침
6 - 4 => 2겹침
7 - 6 => 2겹침
9 - 7 => 2겹침
10 - 10 => 0겹침

1 - 8 삭제
3 - 9 삭제
2 - 2 삭제

하지만 만약 여러개 겹치는 부분을 어떻게 처리할지 생각지 않고 제출하였더니 틀렸다.

풀이

이것은 dp문제 이다.
입력받은 전깃줄을 오름차순 정렬해보자

1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10

왼쪽 전깃줄은 오름차순 정렬이 되었으므로
오른쪽 전깃줄 (8 2 9 1 ...)만 생각하면 된다.

즉 LIS(최장 증가 부분 수열) 을 생각하면 된다.
오른쪽 전깃줄 중 최장 증가 수열은 2 4 6 7 10이 된다.

결국 n - 최장증가수열 길이가 정답이 된다.

for test_case in range(1):
    n = int(sys.stdin.readline())
    lines = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    lines.sort()
    dp = [1 for i in range(n)]
    dp[0] = 1

    for i in range(1, n):
        for j in range(i):
            if lines[i][1] > lines[j][1]:
                dp[i] = max(dp[i], 1 + dp[j])

    print(n - max(dp))