백준 2565번 - 전깃줄

교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제이다.

 

어떻게 하면 전깃줄이 교차되는 지를 생각해보자. 예시에서 A가 1일 때 B가 8이고 2일 때 9인 경우에는 교차하지 않는다. 왜냐하면 A와 B 모두 각각 오름차순이기 때문이다(1~2, 8~9). 반면에 A가 1일 때와 A가 2일 때를 보면 A는 오름차순이지만, B는 각각 8,2로 내림차순이기 때문에 교차한다.

 

어차피 A든 B든 한쪽의 순서는 상관이 없기 때문에, A를 오름차순으로 정렬을 해준 뒤에 문제를 풀어도 된다. 정렬한 뒤 B를 보았을 때 가장 길게 오름차순으로 구성되어있는 수열(가장 긴 증가하는 부분 수열)을 구하면 이 수열이 전깃줄에서 가장 교차하지 않게 구성되어있는 경우가 된다.

즉, 이 수열의 길이만큼을 빼주면 없애줘야 할 전깃줄의 개수를 구할 수 있다.

 

##변수 선언 부분##
data = []
dp = []
LIS = 0
##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    data = [[int(x) for x in input().split()]for y in range(N)]
    dp = [1 for x in range(N)]
    data.sort(key=lambda x: x[0]) #첫번째 원소를 기준으로 정렬해준다.

    for i in range(N):
        for j in range(i):
            if data[i][1] > data[j][1]: #두번째 원소들로 이루어진 수열의 LIS를 구한다.
                dp[i] = max(dp[i], dp[j]+1)
    LIS = max(dp)
    print(N-LIS)

언뜻 보면 어려운 문제이지만, 교차하는 조건을 생각하면 어렵지 않은 문제이다. 만약 이 문제가 LIS와 관련된 문제인 것을 모르고 풀었더라면 체감 난이도가 무척 올라갔을 것 같다.