[백준 2565] - 전깃줄(Gold V)

📜문제

👍풀이

import sys

N = int(sys.stdin.readline())

data = []
for _ in range(N):
    A, B = map(int, sys.stdin.readline().split())
    data.append((A, B))
data.sort()

arr = []
dp = [1 for _ in range(N)]
for d in data:
    arr.append(d[1])

for i in range(N): #LIS를 구하는 Part
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(N-max(dp))

이 문제는 LIS(Longest Increasing Subsequence)라는 유명한 알고리즘을 바탕으로 만든 문제다.

줄이 교차되지 않으려면 A기둥에서 출발한 전선들의 도착점이 증가수열을 이뤄야만 한다. 따라서 B기둥의 도착점들을 A기둥 출발점 기준으로 나열한 다음, B기둥의 LIS 길이 값을 전체 수열에서 빼면 우리가 없애야 하는 전선 수가 나오게 된다!

👍여담

근래 여행을 쭉 갔다오고 리액트 스터디 하는데 나름 집중하다 보니 PS공부에 소홀해진 감이 있었는데, 앞으로 하루에 한 문제씩은 꼭 풀 수 있도록 해야겠다ㅠ