문제
https://www.acmicpc.net/problem/2565
두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.
예를 들어, < 그림 1 >과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.
전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.
출력
첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.
예제
다른 사람의 풀이
N = int(input())
wires = []
dp = [1] * N
for _ in range(N):
wire = list(map(int, input().split()))
wires.append(wire)
wires.sort()
for i in range(1, N):
for j in range(i):
if wires[i][1] > wires[j][1]:
dp[i] = max(dp[i], dp[j] + 1)
print(N - max(dp))핵심 아이디어
전깃줄을 A 순서대로 정렬한다.
A의 순서는 보장되었기 때문에, B만 교차하지 않으면 된다.
-> 현재 순서의 B가 이전 순서의 B보다 크다면 전깃줄이 교차하지 않는다.
즉, A와 B 모두 오름차순으로 정렬되어야 한다.
DP 테이블 초기화
`dp[i]`는 `i`번째 전깃줄까지 봤을 때, 교차하지 않고 설치할 수 있는 전깃줄의 최댓값을 의미한다.
따라서 최소한 자기 자신 하나는 교차하지 않고 설치할 수 있으므로
dp 테이블의 모든 요소를 `1`로 초기화한다.
LIS 알고리즘
A는 이미 오름차순으로 정렬했기 때문에
B가 오름차순으로 이어지는 최장 부분 수열(LIS)이
"서로 교차하지 않는 전깃줄들의 집합"이 된다.
for i in range(1, N):
for j in range(i):
if wires[i][1] > wires[j][1]:
dp[i] = max(dp[i], dp[j] + 1)현재 전깃줄의 B가 이전 전깃줄의 B보다 크다면,
서로 교차하지 않고 이어지는 것이다. (오름차순 조건 만족)
이때 기존의 `dp[i]` 값을 유지하거나,
이전 전깃줄까지의 최대값에 `1`을 더한 값 중에 더 큰 값으로 `dp[i]`를 업데이트한다.
최종 출력값
서로 교차하지 않게 없애야 하는 전깃줄의 최소 개수는
전체 전깃줄의 수 - 교차하지 않고 남는 전깃줄의 최대 개수로 구할 수 있다.
회고
- 전깃줄이 교차하는지를 어떻게 판별할 수 있는지를 먼저 생각했는데 너무 복잡하게 생각해서 코드로 구현하지 못했다.
- 최소값을 어떻게 구할 수 있을지도 고민했었는데, 최소값이 아닌 최대값을 구해서 `전체-최대값`으로 최소값을 구하는 방법도 있다는 아이디어를 얻었다.