[백준/2565/파이썬] 전깃줄

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

2565번: 전깃줄

Problem

• 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.
• 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

조건

• 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

SOL

 

Greedy하게 접근 (반례발생)

 

전선을 꼬이지 않게 배치할 수 있는 방법이 무엇이 있을까를 생각해보면, A->B로 가는 함수관계(고등학생때) 문제가 생각이 나서, 서로 교차가 되지 않으려면, 위의 숫자가 선택한 숫자보다 큰 숫자를 선택해야한다. 

하지만, 이 생각은, A,B 모두 순서대로(오름차순이든,내림차순이든)있는 상태여야한다. 그리고, 문제는 새로연결하는게 아니라, 연결하는 대상을 지정해놓은 상태에서, 나중에 제거할 때의 상태를 보는 방식이다.

 

그래서, 시작점보다, 연결하는 곳이 더 크다면, 그 지점은 교차점이 생길 확률이 크기 때문에, 제외하는 방식으로 구현을 처음에 해줬다. ( 이렇게되면, 애초에 교차가 되지 않는다). 그리고, 전에 연결한 곳을 기억해놨다가,  교차될 가능성이 있으면 바로 제외해주는 방식으로 구현을 하였다.

즉, 매번 연결할 때마다, 교차가 아예 생기지 않는 방향으로 구현을 해주었다.

 

Greedy 방법은 반례가 1개라도 나온다면, 틀린 풀이이다. 왜냐하면, 항상의 Optimal한 방법이, 최적의 Optimal이 되는 과정을 증명하는 과정에서, 반례가 생기면 안되기 때문이다.

틀린 code

#전깃줄
# 많이 꼬인것 부터 접근하면, 반례가 생김

import sys
input= sys.stdin.readline

N=int(input().rstrip())
seq=[list(map(int,input().split())) for _ in range(N)]

seq.sort()
INIT=sys.maxsize
connect=INIT
cnt=0
for a,b in seq:
    if a<b:
        cnt+=1
        continue
    else:
        if connect==INIT:
            connect=b
            continue
        if b<connect:
            cnt+=1
            continue
        connect=b

print(cnt)

 

반례)

5
1 3
3 1
2 5
4 6
6 4

위와 같은 경우, 내가 구현해준대로, 빨간색을 제외하는것보단, 파란색을 제외해주는게 최소의 전선을 배제해주는 방법이다.

 

전선이 교차 되지않을 조건

 

greedy한 방법이 아니니까, 일반화를 조금 시켜보자.  t1<t2라면, t1<t2의 순서를 유지하는게  전선이 교차가 되지 않는다. (t1>t2인 경우도 마찬가지)

• A (t1,t2) 에서, t1<t2 라면, B(t1,t2)에서 또한, t1<t2 이어야 한다.
• A (t1,t2) 에서, t1>t2 라면, B(t1,t2)에서 또한, t1>t2 이어야 한다.

그렇다면, A가 오름차순으로 정렬된 상태라면, B 또한, 증가하는 형태를 이루어야 한다. 어, 그럼, 두번째 원소가 LIS를 이루면 교차되지 않고, 제일 많이 전선을 연결할 수 있게 된다.  그렇다면, 전체의 갯수 - 전선이 교차되지 않는 경우를 해주면, 내가 원하는 답이 구해진다.

 

DP의 LIS 문제가 되버렸다.

 

LIS를 구현하는 방법은 이분탐색을 이용하는 방법, DP를 이용해서 이중포문으로 구현하는 방법 등의 방법이 있다.

여기선 간편하게 이중포문으로 구현하였다.

# DP
import sys
input = sys.stdin.readline

N= int(input().rstrip())
seq=[list(map(int,input().split())) for _ in range(N)]
DP=[1 for _ in range(N)]

seq.sort()
for i in range(N):
    for j in range(i):
        if seq[i][1] >seq[j][1]:
            DP[i]=max(DP[i],DP[j]+1)

print(N-max(DP))