https://www.acmicpc.net/problem/2565
n=int(input())
dp=[0]*n
edges=[]
for i in range(n):
a,b=map(int,input().split())
edges.append((a,b))
dp[i]=1
edges.sort()
for i in range(n):
for j in range(0,i):
if edges[i][1]>edges[j][1]:
dp[i]=max(dp[j]+1,dp[i])
print(n-max(dp))
전깃줄을 각 주어진 양쪽의 점을 이어서 연결되어 있을 때, 전깃줄이 서로 겹치지 않도록 지워야 되는 전깃줄의 최소 갯수를 구하는 문제이다.
지워야 하는 전깃줄의 최소의 갯수라는 것은 즉, 겹치지 않고 연결되는 전깃줄의 최대 갯수를 의미하기도 한다. 또한 시간지워야 하는 전깃줄의 최소의 갯수라는 것은 즉, 겹치지 않고 연결되는 전깃줄의 최대 갯수를 의미하기도 한다. 또한 시간 복잡도 상으로도 이중 for문이 사용되어도 좋을 범위이기도 하고 최소로 DP를 구하기는 어려워보이기 때문에 이처럼 접근하는 것이 좋다.
현재 줄부터 탐색하며 마지막 줄까지 LIS를 사용하면 좋다. 즉, 겹치지 않는 조건하에서 최대로 연결될 수 있는 전깃줄을 찾아나가면 되는 것이다. 여기서 겹치지 않는 조건이란 현재의 전깃줄보다 앞점이 앞에 있으면서 뒷점이 뒤에 있다면 겹치게 되는 것이기 때문에 이중 for문으로 이를 확인하면 된다. 즉, 겹치지 않는다면 전의 이어지는 전깃줄의 수의 최댓값에 +1을 해주면 현재까지 전깃줄을 보았을 때의 최댓값이 된다.
이렇게 Python으로 백준의 "전깃줄" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊