[백준/Python] 2565 전깃줄

[백준/Python] 2565 전깃줄

정답 코드 및 설명

전체 코드

n = int(input())
connections = []
for _ in range(n):
    a,b = map(int, input().split())
    connections.append((a,b))

# a 전봇대 기준으로 정렬
connections.sort()

# b 전봇대 위치만 추출
b_positions = [b for a,b in connections]

dp = [1] * n
for i in range(n):
    for j in range(i):
        if b_positions[i] > b_positions[j]:
            dp[i] = max(dp[i], dp[j] +1)

print(n - max(dp))

풀이 설명

전깃줄이 교차 하지 않을려면 어떻게 해야할까?

한 전봇대에서 연결 순서가 다른 전봇대에서도 증가하는 순서로 연결되어야 한다.

즉, 한 전봇대에 대해서 연결 위치를 기준으로 정렬한 후, 다른 전봇대에 대해서 연결 위치의 최장 증가 부분 수열(LIS) 를 찾는다. 찾은 LIS 의 길이는 최대로 교차하지 않는 전깃줄의 수가 된다.

전체 전깃줄에서 찾은 LIS 길이( = 최대로 교차하지 않는 전깃줄 수) 를 빼준다면 제거해야할 전깃줄 수의 최소가 나오게 된다.

코드 설명

1. 전깃줄의 갯수와 각 전깃줄의 A,B 전봇대에 연결된 위치 정보를 입력받는다.
2. 입력받은 연결 정도를 A 전봇대 위치 기준으로 오름차순으로 정렬한다.
3. B 전봇대의 위치 정보만 빼서 배열을 생성한다.
4. 생성된 배열에 대해 LIS 를 찾는다.
5. 전체 전깃줄 개수 에서 LIS 길이를 빼서, 교차하지 않게 하기 위해 제거해야할 전깃줄의 최소 개수를 계산하고 출력한다.