[BOJ/백준] 2565 전깃줄

# 2565 전깃줄

N = int(input())
dp = [0]*501
arr = []
for _ in range(N):
    n1,n2 = map(int,input().split())
    arr.append((n1,n2))
arr.sort()
result = []
result.append(arr[0][1])
temp = 0
for k1,k2 in arr[1:]:
    for ind,val in enumerate(result):
        if val > k2 and k2 not in result:
            result[ind] =k2
            temp = 0
        elif val < k2 and k2 not in result:
            temp = k2
    if temp:
        result.append(temp)
    temp = 0


print(N-len(result))

개인적으로 어려워 하는 LIS 계열의 문제였다.

전깃줄 A를 기준으로 sort를 해준 다음에,  전깃줄 B를 기준으로 가장 긴 증가하는 수열의 구해주면 된다.

 

그렇게 되면, 선이 꼬이지 않고 설치할 수 있는 최대수가 되고, 주어진 N에서 최대수를 빼주면 된다.

 

코드 자체를 설명해보면 초기값으로 가장 첫번쨰  B 전깃줄을 넣어주고,

 

전체 데이터 들어진 행렬을 반복문을 돌리면서, LIS가 저장된 값과 비교를 하면서 LIS에 저장된 값보다 적으면 바로 그자리를  교체 해준다. 그리고 LIS가 저장된 값보다 전부다 크면 끝에 추가해주면 된다.

 

이 방법은 실제 LIS의 수열을 구하는 것이 아닌, 최장 길이를 구하기 위한 O(Nlogn)의 방식이다. 만약 실제 LIS를 구해야 하는 경우에는 다른 풀이를 찾아야한다.