BOJ 20892 Julklappsköp

문제 링크:

문제 내용

당신은 $K$ 명의 친구에게 선물을 하나씩 사 주기 위해 선물 가게에 왔습니다. 이 가게는 $N$ 종류의 물건을 정확히 하나씩 가지고 있습니다.

각 물건을 각 친구에게 주었을 때 그 친구의 만족도를 모두 알고 있을 때, 모든 친구의 만족도의 합을 최대화하도록 각 친구에게 줄 물건을 골랐을 때의 만족도의 합을 구하세요.

입력

첫 번째 줄에 $K$ 와 $N$ 이 주어집니다. ( $1 \le K \le 14$ , $1 \le N \le 100\;000$ )

두 번째 줄부터 $K$ 개 줄에 걸쳐서 각 줄에 $N$ 개의 정수 $a_{ij}$ 가 주어집니다. $i$ 번째 줄의 $j$ 번째 값 $a_{ij}$ 는 $i$ 번째 친구에게 $j$ 번째 물건을 선물했을 때 그 친구의 만족도를 나타냅니다. ( $0 \le a_{ij} \le 10^8$ )

출력

문제의 정답을 출력합니다.

문제 풀이

풀이 1

Min-cost Maximum Flow로 모델링하면, $K+N$ 개의 정점과 $KN$ 개의 간선을 갖는 플로우 그래프가 만들어지는데, 이때 $V$ 는 약 10만, $E$ 는 약 140만이 되므로, $\mathcal{O}(VE)$ 최단거리 알고리즘을 쓰는 일반적인 MCMF 구현체로는 해결하기 어렵습니다.

다음과 같은 관찰을 통해 선물의 후보를 줄일 수 있습니다.

$K$ 개의 선물을 고른 상태에서, $i$ 번째 친구가 받은 선물보다 더 나은 선물이 아직 안 준 선물 중에 존재한다면, $i$ 번째 친구의 선물을 교체할 수 있습니다.
어떤 친구가 그 친구의 선호도 순으로 정렬했을 때 상위 $K$ 개 밖에 있는 선물을 받았다면, 항상 상위 $K$ 개 이내의 선물로 바꿀 수 있습니다.
따라서, 각 친구의 선호도 순으로 상위 $K$ 개 내에 있는, 총 $K^2$ 개의 선물로 고려 범위를 좁힐 수 있습니다.

이렇게 하면 $V$ 가 약 200, $E$ 가 약 3000이 되어 MCMF로 풀 수 있는 문제가 됩니다.

$K \le 14$ 를 이용하여 비트 DP로도 풀 수 있습니다. 각각의 선물을 하나씩 추가하거나 추가하지 않으면서 어떤 친구의 집합에게 줄 선물을 골랐을 때의 최대 합을 구하면 $\mathcal{O}(2^K K^3)$ 에 풀 수 있습니다.

풀이 2

MCMF에서 퍼텐셜을 이용하여 벨만 포드 또는 SPFA 대신에 Dijkstra를 쓰는 방법이 있습니다. 이러한 구현체를 이용하면 선물 후보를 좁히는 위 풀이의 과정을 거치지 않고도 문제를 풀 수 있습니다.

Last updated on 2026년 3월 5일 13:43:54

BOJ 20660 Pizza BOJ 20953 고고학자 예린