#157 백준 파이썬 [2565] 전깃줄 - LIS

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

 

#Solution

LIS를 이용해 간단하게 풀 수 있다.

가장 적은 전깃줄을 없애는 방법은 <가장 많은 전깃줄을 그대로 놔두는 방법>을 구하는 것과 동일하다.

[A, B] 리스트를 만들고 A 오름차순으로 정렬해준 뒤,

각 항에 대하여 B의 가장 긴 증가하는 수열을 구해준다.

 

예를 들어 위 식은 아래와 같이 먼저 정렬된 뒤,

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

각 항의 가장 긴 증가하는 수열을 구해주게 된다.

A	B	증가 수열
1	8	8
2	2	2
3	9	2 9
4	1	2 9
6	4	2 9
7	6	2 4 6
9	7	2 4 6 7
10	10	2 4 6 7 10 or 1 4 6 7 10

가장 긴 증가하는 수열(2, 4, 6, 7, 10)을 만들기 위해 총 8개의 line 중 3개만 끊어주면 된다.

line = int(input())
AB_line = []

for _ in range(line):
    A, B = map(int, input().split())
    AB_line.append([A,B])

#A오름차순으로 정렬
AB_line = sorted(AB_line, key = lambda x: x[0])


#LIS를 구해주자
result = [[] for _ in range(line)]
for i in range(line):
    if i == 0:
        result[i].append(AB_line[i][1])
    else:
        for j in range(0, i):
            if result[j][-1] < AB_line[i][1]:
                if len(result[i]) - 1 < len(result[j]):
                    result[i] = result[j] + [AB_line[i][1]]
        if not result[i]:
            result[i].append(AB_line[i][1])


#가장 긴 수열
maximum = 0
for i in range(line):
    maximum = max(maximum, len(result[i]))
print(line - maximum)