[1150] MCMF 없이 백업 증명하기

https://www.acmicpc.net/problem/1150
 
 
굉장히 재밌었던 문제기도 했고 널리 알려진 MCMF 증명말고도 다른 방법으로도 증명할 수 있는거 같아서 글을 남깁니다. 
틀린 부분 있으면 지적해주시면 감사하겠습니다!
 

문제요약 및 풀이

$N$개의 회사들의 위치가 주어졌을때 $K$개의 케이블을 이용해서 $2K$개의 회사를 한 쌍으로 매칭시키는 문제입니다. 이 과정에서 케이블의 길이는 최소화되어야합니다.
 
풀이는 다음과 같은 작업 중 비용이 최소인 경우를 하나 선택하는걸 $K$번 반복해주면 됩니다.
 

• 아직 케이블로 연결된 적이 없는 인접한 두 회사를 케이블로 연결한다. 이때, 비용이 가장 작은 경우를 택한다.
• $p$개의 인접한 회사들이 전부 연결되어 있다고 가정하고 여기서 가장 왼쪽에 있는 회사를 $l$번 회사, 가장 오른쪽에 있는 회사를 $r$번 회사라고 하자. 이때 $l-1$번 회사와 $r+1$번 회사가 아직 연결되지 않았다면 $l-1$번 회사에서 $r+1$번 회사까지 케이블을 반전시킨다. 이 역시 비용이 가장 작은 경우를 택한다.
• (반전이라는게 약간 애매한데 인접한 회사끼리 서로 연결된 경우를 A, 그렇지 않은 경우를 B라고 놨을때 BABAB...AB를 ABABA...BA로 바꾸는걸 의미합니다. 이 과정에서 A가 하나 더 많아지므로 케이블을 하나 추가한 것과 같은 효과를 낸다는건 쉽게 알 수 있습니다.

간단한 풀이지만 풀이의 정당성을 증명하는건 어렵습니다. (구현도 어렵습니다.) 
 

증명

MCMF 말고 다르게 증명해봅시다.
 
우선, 케이블을 정확하게 $k$개 사용했을 때 나올 수 있는 모든 경우에서의 최솟값을 $o(k)$라고 정의하고, 위에 풀이를 이용해서 $k$개 골랐을 때 나오는 값을 $g(k)$라고 놓겠습니다. 
 
기저는 $k=1$일때며, 이때는 자명하게 $g(1)=o(1)$입니다.
임의의 p에 대해서 $k \leq p$라면 $g(k)=o(k)$임을 안다고 가정합시다. $g(p+1)=o(p+1)$가 됨을 보일 수 있다면 풀이가 정당함을 증명할 수가 있습니다.
먼저 $o(p+1)-o(p)$ 즉, 케이블이 $p$개에서 $p+1$개로 늘었을 때 증가하는 최적해의 비용을 $f$라고 놓읍시다. 여기서 나올 수 있는 경우는 2가지 입니다.
 

i) 길이가 $f$인 케이블을 새로 추가할 수 있는 경우
 

자명하게 $g(p+1)=g(p)+f=o(p+1)$입니다. 
 

ii) 길이가 $f$인 케이블을 추가할 수 없는 경우

 
추가하는 작업은 사용할 수 없기 때문에 간선을 반전 시켜서 딱 $f$만큼만 비용을 증가시키는 방법이 반드시 존재함을 보여야합니다. 재미있는 lemma를 하나 증명하고 가봅시다.
 
lemma) $p+1$개의 케이블로 $o(p+1)$를 만들어내는 케이블들의 집합을 $E_o$, 위의 풀이를 반복해서 $p$개의 케이블을 추가했을 때 사용된 회사들의 집합을 $V_g$라고 하자. 길이가 $f$인 케이블을 추가할 수가 없다면 $E_o$에 들어있는 모든 케이블들은 $V_g$에 들어있는 회사를 반드시 하나 이상 포함하고 있다.
 
만약 $E_o$에 들어있는 케이블 중에서 $V_g$에 들어있는 회사를 하나도 포함하고 있지 않은 케이블이 있고 그 케이블의 길이가 $e$라고 가정해봅시다.
만약 $e$ > $f$라면 $k \leq p$인 임의의 k에 대해서 $o(k+1)=o(k)+e$ 인 경우가 존재한다는 뜻인데, 이를 $o(k+1)=o(k)+f$로 바꾸면 기존의 $o(k+1)$보다 더 최솟값이 되므로 모순입니다. 
남은 경우는 $e$<=$f$인데 이미 이 케이블이 $V_g$에 속한 회사를 하나도 포함하고 있지 않다고 했으므로 e는 추가가 가능한 케이블입니다. 그렇다면 $g(p)+e<=o(p+1)$가 되며, $o(p+1)$이 최솟값이라는 거에 모순이 됩니다. 
2가지 경우 전부 다 모순이 생기므로 해당 경우는 존재할 수가 없습니다. 따라서 lemma가 증명이 됩니다.
 
 
위에 lemma에 따르면 케이블을 한개 더 추가해서 $o(p+1)$을 만들었다고 했을 때 $g(p)$와 비교해 봤을 때

1. $o(p+1)$이랑 $g(p)$가 정확하게 같은 회사를 연결하는 경우
2. $o(p+1)$은 $(i,i+1),...,(i+k-1,i+k)$를 연결하고, $g(p)$는 $(i+1,i+2),...,(i+k,i+k+1)$를 연결하는 경우
3. $o(p+1)$은 $(i,i+1),...,(i+k-1,i+k)$를 연결하고, $g(p)$는 $(i-1,i+1),...,(i+k-2,i+k-1)$를 연결하는 경우
4. $o(p+1)$은 $(i,i+1),...,(i+k-1,i+k)$를 연결하고, $g(p)$는 $(i-1,i+1),...,(i+k,i+k+1)$를 연결하는 경우
5. $o(p+1)$은 $(i,i+1),...,(i+k-1,i+k)$를 연결하고, $g(p)$는 $(i+1,i+2),...,(i+k-2,i+k-1)$를 연결하는 경우

위에 다섯 가지 경우가 섞여서 존재하게 됩니다. 
 
lemma 하나 더 증명하고 갑시다.
 
lemma) 임의의 구간을 잡았을 때 그 구간안에서 $o(p+1)$를 만들기 위해 사용한 케이블의 개수와 $g(p)$를 만들기 위해 사용한 케이블의 개수가 같다면 그 구간에서 케이블들의 길이의 합은 동일하다. 
 
임의의 구간을 잡았고, 그 구간 내에서 둘의 케이블의 개수가 같을 때 $o(p+1)$에서 사용된 케이블들 길이의 합을 $X$, $g(p+1)$에서 사용된 케이블들의 길이의 합을 $Y$라고 합시다.
$X>Y$, $X<Y$ 둘 다 값이 큰 쪽을 값이 작은 쪽으로 되게 끔 이동시키면 이전보다 더 작은 값을 만들어 낼 수가 있게 되는데 $X>Y$에 경우에는 $o(p+1)$이 최적해라는 것에 모순이 되고, 반대로 $X>Y$라면 $g(p)$ 값을 좀 더 작게 만들어 낼 수가 있는데, 이미 $g(p)=o(p)$, 즉 최적해랑 같은 결과를 낸다고 했으므로 $o(p)$를 더 작게 만든다는 뜻이 되어서 결국 똑같이 모순입니다.
가능한 경우는 $X=Y$밖에 존재하지 않게되므로 증명이 끝납니다.
 
 
위의 lemma에 따르면 1,2,3번은 더 이상 고려할 필요가 없습니다. 개수가 같기 때문에 값은 반드시 같을 수 밖에 없기 때문입니다.
따라서 1,2,3번의 경우는 무시해도 상관없습니다. 4번과 5번만 있다고 가정하고 결론을 내려봅시다.
4번과 5번이 인접해있다면 그 둘을 묶은 구간 안에서의 케이블의 개수는 $o(p+1)$과 $g(p)$가 서로 같기 때문에 lemma에 따라서 케이블 길이의 합이 동일할 수 밖에 없습니다. 따라서 이 둘 역시 제외시켜 줄 수가 있습니다.
또한, $o(p+1)$의 케이블의 개수와 $g(p)$의 케이블의 개수는 정확하게 하나 차이가 나고 이는 곧 4번의 경우가 5번의 경우보다 정확하게 하나 많다는 것을 의미합니다. 결국 인접한 4번, 5번을 계속 지워주는 과정을 반복할 수가 있고 이 과정을 통해서 5번 하나만 남게 됩니다.
마지막으로 하나 남은 5번을 반전시켜주면 1번과 같은 모양을 띄게 되므로 $o(p+1)$과 $g(p+1)$의 값이 동일하다는 것을 보일 수 있습니다. 이걸로 증명이 끝납니다.