[Python]동적계획법 백준 2565

  문제

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

이문제는 바로 풀려고 하면 매우 복잡해진다.

정답률은 높은데 나는 어려웠다.

간단히 생각하면 가장 적게 자르기 위해선 겹치지 않고 가장 많이 연결됬을때이다. 

겹치지 않는다는건 A를 기준으로 정렬해 봤을때 B가 오름차순으로 가장 많이 연결되었을

때 이다.정렬을 하여 보게되면 익숙한 문제로 보이게 된다.

앞서 봤던 가장긴 수열과 같다.

답을 쓸때 전깃줄수에서 가장 많이 연결됬을때의 길이를 빼주면 된다.

아래 사이트의 풀이를 참조했다.

#https://claude-u.tistory.com/206

아직도 부족함이 많이 느껴진다.

import sys
 
 
n=int(sys.stdin.readline())
 
e_line=[list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#교차한 개수 구하기
#모두 구해진 교차개수에서 가장많이 교차된 전깃줄부터 자르기
 
#https://claude-u.tistory.com/206
result=[0 for _ in range(n)]#B에대해 오름차순으로 정렬했을때 가장긴거
e_line=sorted(e_line,key=lambda x:x[0])#A를 기준으로 정렬
 
 
for i in range(n):
    max_value=0
    for j in range(i):
        if e_line[i][1]>e_line[j][1]:#A를 기준으로 정렬됬다면 B를 기준으로 가장긴 수열을찾는다.
            if max_value<result[j]:
                max_value=result[j]
    result[i]=max_value+1
 
 
print(n-max(result))