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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net


인터넷에 작성된 풀이들은 그리디 전략에 도달하는 과정을 제대로 설명하지 않은 것 같고 저처럼 이런 유형을 처음 접하여 한참동안 헤매는 사람들의 이해를 조금이라도 돕기 위해 작성해봅니다


사전지식:

이 풀이는 독자가 MCMF를 완벽하게 이해하고 있다고 가정하고 쓰여진 풀이지만 사실상:

  1. 플로우의 개념

  2. MCMF 알고리즘이 작동하는 원리

    1. 유량을 흘릴 때마다 최단경로를 찾는다

  3. MCMF 알고리즘이 항상 최적해를 찾는다는 사실

만 알고 있어도 이해하는데 문제 없게 쓰려고 노력했습니다.



문제 요약:


본 풀이는 이 요약에서 쓰여진 단어들을 사용할 것이기 때문에 문제를 알고 계셔도 한번 읽어주세요


길이 N (N<=1e5)의 수열이 주어진다. 모든 인접한 원소들의 쌍 (N-1개) 에 대한 비용이 주어진다.

쌍들의 비용의 합을 최소화하게 K (K<=N/2)개의 쌍을 고르고, 이때 비용의 합을 출력하라. 다만, 모든 쌍들은 겹치지 않아야 한다 (예. [1,2], [3,4] OK [1,2],[2,3] NOT OK)


풀이:


우선 바로 N^2 DP 등의 나이브한 풀이는 통과하기 어려운 문제란걸 볼 수 있다. 그럼, 문제의 조건을 살펴보자. 어느 부분에서 최적화를 시킬 수 있을까?


위 사진을 보자. [A,B], [B,C], [C,D]의 원소들의 쌍들을 살펴봤을때, [A,B]와 [C,D]를 고르거나 [B,C]를 고를 수 있다. 다른 말로 하면, [A,B]와 [B,C]중 단 하나의 쌍이 쓰여질 수 있고, [B,C]와 [C,D]중 단 하나의 쌍이 쓰여질 수 있다는 말이다. 이를 일반화하자면, 임의의 원소를 공유하는 두 쌍 중 무조건 하나만 쓰일 수 있다.


MCMF 응용 문제들을 풀어 보셨다면 ‘어? 둘 중 하나만 쓸 수 있다고? 그거 완전 MCMF 모델링인데?’라고 생각하셨겠죠. 그 말이 맞습니다. (여기서 바로 MCMF로 넘어가는게 부자연스럽다고 느끼신다면 MCMF 모델링을 기반으로 둔 그리디인 만큼 언급했던 두부장수 장홍준 같은 문제들을 조금 접해보고 다시 도전하는것도 나쁘지 않다고 생각합니다).


ABCD 예제는:


같이 유량 그래프로 바꿀수 있겠죠 (모든 간선의 유량 상한은 1, 원소들을 연결하는 간선들의 비용은 쌍의 비용의 값).


B에서 Sink로 흘려보낼 수 있는 유량은 1이 최대기 때문에 [A,B]나 [B,C]중 하나만 보낼수 있게 하고 있죠. 비슷한 원리로, Source에서 C로 흘려보낼 수 있는 유량은 1이 최대기 때문에 [C,B]나 [C,D]중 하나만 보낼 수 있습니다.


이는 다음과 같이 N개의 원소의 수열로 일반화 할 수 있습니다.



이렇게 만든 그래프는 O(N) 간선들과 정점들을 가지고 있습니다. N은 십만까지 올라갈수 있습니다. 당연히, 플로우 알고리즘으로 해결이 불가능한 문제입니다 (일반적으로 시복의 상한보다 훨씬 빠르게 돈다는 점을 고려해도 O(V^2 E)는… ㅎㅎ)


그럼 또 다시 이 그래프에서 유량을 흘렸을때 최단 경로를 어떠한 방식으로 찾는지 봅시다.



우선 한개의 유량을 흘린 뒤 다음부터 흘릴 유량의 최단경로는 다음 두 가지의 유형이 있습니다.


다음과 같이 전에 나왔던 쌍들과 겹치지 않는 경우 (그냥 최소 비용을 더해주면 됨)

다음과 같이 전에 나왔던 쌍을 적당히 옮겨 새로운 쌍을 넣는 경우


수열로 표현해 보자면 이러한 식으로 바뀌었다.

이러한 식으로 벌써 흘렀던 유량을 취소하고 새로운 쌍들을 추가한다. 그래프의 구조를 살펴보면 보이겠지만, 항상 이러한 식으로 쌍들을 옆으로 한 칸 밀어서 새로운 쌍을 배치하는게 최적이란걸 볼 수 있다.


다음과 같이 우리는 ‘탐욕적이게' 그 당장 순간에 벌써 내려놨던 쌍을 옆으로 한 칸 옯겨서 다른 쌍을 내려놓거나, 벌써 내려놓지 않은 쌍의 비용들 중 최소의 값을 반복적으로 찾는 과정으로 최적해를 찾을 수 있다는 사실을 증명했다. 이를 구현하는것도 쉬운 일이 아니지만, 이는 독자의 숙제로 남기겠다. 글쓴이도 좀 구리게 구현해서 밝히기 부끄럽다는 사실을 감안해서 봐주세요