[백준] 2565번 - 전깃줄 (DP) - 결과 포함

www.acmicpc.net/problem/2565

2565번: 전깃줄

감이 안 와서 다른 분들의 블로그를 참고했다.

결과적으로 이전에 했던 가장 긴 증가하는 부분수열을 구하는 방법을 이용하면 됐다.

 

문제는 전깃줄이 겹치지 않도록 전깃줄을 제거하는 최소 갯수를 구하는 것이다.

주어지는 전깃줄 정보가 순서대로 주어지지 않기 때문에 먼저 A 기준으로 정렬을 해준다.

 

그리고 A에 연결된 B의 정보를 훑으면서 증가하는 수열을 찾는다.

전깃줄이 꼬이지 않는 경우는 B의 숫자가 계속 증가하는 경우다.

A 1번과 B 2번

A 2번과 B 3번

A 3번과 B 4번

이런 식으로 모든 전깃줄이 계속 증가하는 모습을 가지고 있다면 전깃줄은 꼬이지 않는다.

 

가장 긴 증가하는 부분 수열의 길이를 찾는다면 이 수열은 꼬이지 않고 가장 길게 유지하는 수열이다.

이 수열이 꼬이지 않고 최대로 유지하는 부분이기 때문에 모든 전깃줄에서 이 부분을 빼면

꼬이지 않기 위해 제거해야 하는 최소한의 전깃줄 갯수를 구할 수 있다.

 

따라서 B에 연결된 전깃줄 정보를 순회하면서 가장 긴 증가하는 부분 수열을 찾는다.

그 다음 이 수열의 길이를 전체 전깃줄 수에서 뺀다.

 

[소스 코드]

n = int(input())

data = []
d = [1] * n

for i in range(n):
    data.append(list(map(int, input().split())))

data.sort()

for i in range(n):
    for j in range(i):
        if data[i][1] > data[j][1]:
            d[i] = max(d[j] + 1, d[i])

print(len(data) - max(d))