백준 2565 전깃줄 Python3

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

2565번: 전깃줄

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2565.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

n = int(input())
lines = []
for _ in range(n):
    lines.append(list(map(int, input().split())))

lines.sort(key = lambda x:x[0])
dp = [1]*n
for i in range(1, n):
    for j in range(i):
        if lines[i][1] > lines[j][1] and dp[i] < dp[j]+1:
            dp[i] = dp[j]+1
print(n-max(dp))

---

풀이 과정

n = int(input())
lines = []
for _ in range(n):
    lines.append(list(map(int, input().split())))
#A 전봇대 기준으로 전깃줄 오름차순으로 정렬 -> T(n) = nlogn
lines.sort(key = lambda x:x[0])
#0~i번까지의 전깃줄 중 i와 교차하지 않고 연결할 수 있는 전깃줄의 개수를 메모이제이션
dp = [1]*n
for i in range(1, n):
    for j in range(i):
        if lines[i][1] > lines[j][1] and dp[i] < dp[j]+1:
            dp[i] = dp[j]+1
#교차하지 않고 연결할 수 있는 전깃줄 개수의 최댓값을 전체 전깃줄에서 뺴주는 것이 없애야하는 전깃줄의 최소 개수이다
print(n-max(dp))
#시간복잡도 = O(n^2), 공간복잡도 = O(n)