코드

n = int(input())

cable = []

# 전깃줄 연결 상태 입력
for _ in range(n):
    cable.append(list(map(int, input().split())))

# 첫번째 요소를 기준으로 cable 정렬
# 이차원 배열을 sort() 시키면 첫번째 요소로 정렬됨
cable.sort()

# 두번째 전봇대에 연결된 전깃줄 위치만 따로 입력받을 리스트
second_pole = []

for i in range(n):
    second_pole.append(cable[i][1])

# DP 테이블
d = [1 for _ in range(n)]

# LIS 메소드
def lis(pole, d):
    for i in range(1, n):
        for j in range(i):
            if pole[j] < pole[i]:
                d[i] = max(d[i], d[j] + 1)
    return d

lis(second_pole, d)

# LIS의 값만큼 전깃줄 개수에서 뺴주면 정답
print(n - max(d))

문제 해설

LIS의 응용 문제.

코드 구현 자체는 그리 어렵지 않으나, 문제를 푸는 힌트를 얻는게 어려운 문제이다.

일단 입력받은 전깃줄 연결 상태를 하나의 전봇대를 기준으로 오름차순 정렬을 한 후, 나머지 한 전봇대의 연결 상태의 LIS를 구해줘서 나오는 값이 교차되지 않게 전깃줄을 설치할 수 있는 최대 개수가 된다. 문제에서는 교차되지 않게 만들기 위해 제거해야 하는 최소 개수를 구하라고 하였으므로, 입력받은 전깃줄의 개수 n에 LIS로 구한 값을 빼주면 정답으로 인정된다.

댓글남기기

참고