백준 2565 전깃줄

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

2565번: 전깃줄첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는www.acmicpc.net

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

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

‘가장 긴 부분 증가수열을 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]=tmpmax_dp=max(dp)print(n-max_dp)

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