[알고리즘] 백준 2565 전깃줄

https://www.acmicpc.net/problem/2565

문제를 풀면서 처음 생각했던것은 입력받은 전기줄을 0번 인덱스 또는 1번 인덱스로 정렬한 뒤, 현재 연결된 전깃줄보다 다음 전깃줄 중에서 연결된 전깃줄의 번호가 작다면, 현재 위치에서 제거한 전깃줄의 최소 갯수를 dp 리스트에 저장하는 방법을 생각하였다.

그러나 반례가 생겨 잘 풀리지 않아, 풀이를 찾아보게 되었다.

정렬을 한다는 접근법은 맞았으나, 점화식 정의에 대한 기준이 잘못되었다.

이 문제는 전깃줄 정렬 이후에는 이 전에도 계속 연습해왔던 LIS(최장 증가 부분 순열)과 동일하게 풀면 문제가 풀린다.

예를 들어 입력이 아래와 같다고 가정하자.

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

이를 0번 인덱스를 기준으로 정렬한다.

[1, 8]
[2, 2]
[3, 9]
[4, 1]
[6, 4]
[7, 6]
[9, 7]
[10, 10]

이후에는 0번을 기준으로 정렬했기 때문에, 이후에는 1번 인덱스의 값들을 가지고 비교해보면 된다.

8 2 9 1 4 6 7 10

이렇게 정렬한 뒤, 내가 처음 생각했던것처럼 만약 현재 숫자가 다음에 나오는 숫자들보다 크다면 교차가 생기는것이므로 해당 전깃줄을 잘라내는것으로 간주하면 된다.
이는 조금만 생각해보면 LIS와 동일하다는것을 알 수 있게 된다.
위 순열에서 LIS는 2 4 6 7 10과 1 4 6 7 10 두 개의 길이 5인 LIS가 나온다.

여기서 LIS에 해당하는 전깃줄은 교차되지 않는 전깃줄의 집합이기 때문에, 전체 전깃줄 개수인 8에서 5를 빼준 3이 위 예제의 정답이 된다.

다른 예제에서도 마찬가지로 전체 (전깃줄 갯수 N)-(LIS 길이) 이 최종 정답이 된다.

정답 코드

import sys

N = int(sys.stdin.readline())

lines = []
for _ in range(N):
    lines.append(list(map(int, sys.stdin.readline().split())))

lines.sort()
print(lines)
temps = []
for i in range(N):
    temps.append(lines[i][1])
print(temps)
dp = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if temps[i] > temps[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(N - max(dp))

풀이를 알고 난 뒤에는 쉬운 문제였지만, 문제를 처음 맞닥뜨렸을때 이 문제가 LIS라는 것을 판단하는것이 쉽지 않았던것 같다.

문제 유형을 파악하는 훈련이 더 필요할 것 같다.