[백준] 2565번:전깃줄 (python 파이썬)

문제

www.acmicpc.net/problem/2565

2565번: 전깃줄

 

풀이

가장 긴 증가하는 수열의 변형? 이라고 생각하면 된다.

먼저, 입력 리스트를 오름차순으로 정렬시킨 후, b 전봇대 기준으로 가장 긴 증가하는 수열을 구한다.

n 에서 그 구한 수열의 길이를 빼주면 된다.

가장 긴 증가하는 수열을 구하기 위해서, B 전봇대 현재 가르키고 있는 위치 숫자보다 작되, 제일 카운트가 큰 숫자에 +1을 해주면 된다.

 

소스코드

import sys
input = sys.stdin.readline

n = int(input())
line = [list(map(int, input().split())) for _ in range(n)]
line = sorted(line, key=lambda x:x[0])
num = [0]*n
for i in range(n):
    max_num = 0
    for j in range(0, i):
        if line[i][1]>line[j][1]:
            if max_num<num[j]:
                max_num = num[j]
    num[i] = max_num+1

print(n-max(num))