[Baekjoon] 2565번 : 전깃줄 (Python)

[Baekjoon] 2565번 : 전깃줄 (Python)

 

목차

 

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

Python

 

방법 1 - 메모리 30864KB / 시간 16ms / 코드 길이 B

 

전기줄이 교차하지 않기위해서는 A 전봇대가 순차적으로 증가할 때, B 전봇대 역시 증가하는 숫자가 돼야한다.

 

이는 LIS의 또 다른 문제 11053, 11054번 문제와 유사함을 알 수 있다.

https://aigong.tistory.com/385

[Baekjoon] 11053번 : 가장 긴 증가하는 부분 수열 (Python)

https://aigong.tistory.com/386

[Baekjoon] 11054번 : 가장 긴 바이토닉 부분 수열 (Python)

 

다만 위 문제들과는 2가지 차이가 있다.

 

1) A 전봇대가 연속적으로 증가한다는 조건을 충족하기 위해 l[0]에 대한 정렬을 진행한다.

2) 출력값으로 연속적으로 증가하는 숫자를 출력하는 것이 아닌 전체 길이 n에서 연속적으로 증가하는 최대값을 뺀 값을 출력해야한다 

 

import sys
input = sys.stdin.readline
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
d=[1]*n
for i in range(n):
    for j in range(i):
        if l[i][1] > l[j][1]:
            d[i] = max(d[i], d[j]+1)
print(n-max(d))