백준 2565 전깃줄

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

2565번: 전깃줄

예전에 비슷한 문제를 읽어봐서 쉽게 풀 수 있었다.

 

문제는 헷갈리지만, 이를 요약하면,

'가장 긴 부분 증가수열을 A를 찾아라' 로 요약할 수 있다.

 

이후 전체 전깃줄에서 A에 속하지 않은 전깃줄을 모두 잘라내면 되므로

 

전체길이-가장 긴 부분증가수열의 길이 가 답이다

 

%%코드%%

 

n=int(input())

elect=sorted([list(map(int,input().split()))for _ in range(n)])
dp=[1 for _ in range(n)]

for i in range(1,n):
    for j in range(i):
        if elect[i][1]>elect[j][1]:
            tmp=dp[j]+1
            if tmp>dp[i]:
                dp[i]=tmp
max_dp=max(dp)
print(n-max_dp)

모르는 알고리즘이면 유추하느라 고생깨나 했을거같다.