2565: 전깃줄

문제 링크

2565: 전깃줄

구현 방식

• DP로 어떻게든 풀어보려고 애를 썼다

• 일단 line을 A 기준 오름차순으로 정렬해줘야한다

• 그 후, 2중 for문을 돌면서 dp table을 갱신해줘야한다

  • outer for loop을 아래에 있는 전깃줄, inner for loop을 위에 있는 전깃줄로 잡았을 때, 위에 있는 B 위치의 전깃줄이 아래에 있는 B 위치의 전깃줄보다 값이 작아야(더 높이 있어야) 전깃줄이 교차하지 않는다
    -> 해당 경우에 dp[i]를 max(dp[i], dp[j]+1)로 갱신해준다

• N - max(dp)의 값이 구하고자하는 정답이 된다

코드

import sys

N = int(sys.stdin.readline()[:-1])
line = []
for n in range(N):
    line.append(list(map(int, sys.stdin.readline()[:-1].split())))
line.sort() # A를 기준으로 오름차순 정렬

dp = [1] * N
for i in range(1, N): #아래
    for j in range(0, i): #위
        if line[j][1] < line[i][1]: dp[i] = max(dp[i], dp[j]+1)
        
print(N - max(dp))

결과