[BOJ/Step15] 2565 : 전깃줄 (Python)

www.acmicpc.net/problem/2565

2565번: 전깃줄

---

허허 리스트에 교차점 다 넣고 지우고 넣고 빼고 난리난리를 쳤는데

반례를 없앨 수가 없어서 대체 어떻게 푸는건가 봤더니

참.. 세상에 이런 방법이..... 똑똑한 사람 개많다 증말 ㅜ

어쩐지 앞에 문제가 뜬금없다 했는데 써먹으라고 알려준거구나....

 

없애야 하는 전깃줄의 최소 개수를 구한다는건

없애지 않고 그대로 놔둘 전깃줄의 최대 개수를 구하는 것과 같다

 

A 전봇대 기준 오름차순으로 정렬했을 때

B 전봇대에 연결된 번호가 오름차순인 가장 긴 전깃줄의 개수를 구하면 된다

즉 앞 문제 11053 : 가장 긴 증가하는 부분 수열 을 구하면 된다

 

1. 전깃줄을 입력받아 wire에 저장, 정렬한다

2. 정렬된 wire의 B 전깃줄 부분을 seq에 저장하고 가장 긴 증가하는 부분 수열을 구한다

3. 전깃줄의 개수 - 가장 긴 증가하는 부분 수열의 길이 를 출력한다

# 2565.py

num = int(input())
wire = [[i for i in map(int, input().split())] for _ in range(num)]
wire.sort()

seq = [i[1] for i in wire]
t_seq = [1] + [0 for _ in range(num-1)]

for i in range(1, num):
    a = [0]
    for j in range(i):
        if seq[j] < seq[i]:
            a.append(t_seq[j])
    t_seq[i] = max(a) + 1

print(num - max(t_seq))