커플 만들기

커플 만들기 문제

알고리즘 풀이하다가 흥미로운 문제가 있어서 기록을 남깁니다.

백준 온라인 저지 1727번 문제^[각주:1]

커플 만들기

문제

여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명을 불러 모아서 이성 친구를 만들어 주기로 하였다. 하지만 아무렇게나 해 줄 수는 없고, 최대한 비슷한 성격의 사람들을 짝지어 주기로 하였다.

당신은 뭔가 알 수 없는 방법으로 각 사람의 성격을 수치화하는데 성공하였다. 따라서 각 사람의 성격은 어떤 정수로 표현된다. 이와 같은 성격의 수치가 주어졌을 때, 우선 최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하려 한다. 남자-여자 커플만 허용된다.

입력

첫째 줄에 n, m(1≤n, m≤1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다.

출력

첫째 줄에 성격의 차이의 합의 최솟값을 출력한다.

예제 입력 1

2 1

10 20

15

예제 출력 1

5

알고리즘 분류

- 다이나믹 프로그래밍

- 정렬

마치 결혼정보회사 같은 곳에서 정말로 쓰고 있을 것 같은 계산법입니다. 수치화된 성격이란 이를 테면 나이 같은 것도 해당할 수 있겠죠. 보통 비슷한 나이 또래를 짝지어 주는 게 바람직하니까요.

문제 시나리오가 참신합니다. 좀 뜬금 없지만 옛날에 부모님이 주말 오전이면 어김 없이 즐겨 보시던 그 텔레비전 프로그램이 기억나네요. 일반인 남자 여자들 나오고 마지막에 막 화살표 쏘는 건데, 제목이 사랑의 스튜디오던가. 당시 나는 어린이여서 그게 엄청 지루하기도 하고 왜 그렇게 인기가 있는지 몰랐어요. 역시 짝을 찾는다는 일은 동서고금을 막론하고 어른들의 최고의 관심사가 아닐까 합니다.

문제에서는 남자친구, 여자친구라고 했지만 신랑, 신부라고 해도 답을 구하는 데에 영향은 없어 보입니다. 그래서 짝을 지어 주는 것에 대해서 편의상 '결혼을 한다'나 '배우자를 찾는다' 같은 표현을 사용하겠습니다.

문제 내용 정리

- 임의의 남자와 여자 후보들이 있고 그 수는 각각 최소 1명 최대 1000명이다.

- 남녀 후보의 데이터가 주어져 있다. 이를 수치화된 성격이라고 한다.

- 수치화된 성격을 통해서 후보 각각은 다른 사람과의 성격 차이를 계산으로 구할 수 있다.

- 성격 값은 자연수이며 최대 100만이다.

- 가능한 모든 남자와 여자를 짝지어 주려고 한다. (여러 가지 조합이 가능하다.)

- 짝지은 커플들의 성격 차이의 합이 최소가 되어야 한다. (즉, 짝지은 커플들의 성격 차이의 합이 최소가 되게 하는 조합을 구하고, 최종적으로 그 조합으로부터 성격 차이의 합을 구해야 한다.)

- 모든 후보는 미혼자이고 일부일처제이며 동성애는 불가능하다. 하나의 커플이 될 수 있도록 짝지어 주는 것은 남자와 여자를 일대일로 이어 주는 경우밖에 없다.

가정1)

이런 문제를 풀 때 보통 처음 생각하는 것은 모든 경우의 수를 단순하게 모두 시도해 보면 어떨까 하는 것입니다. 남자나 여자 그룹 중 하나를 순열로 두고 그 순열의 모든 조합을 구해서 순서대로 1대1 매칭시킨다고 해 봅시다.

예를 들어 (그 생각을) 그림으로 나타내면 이런 모양이 됩니다.

크기가 N인 순열을 돌릴 때 시간복잡도는 O(N!) 쯤 된다고 들었습니다. 그리고 남녀의 수는 각각 최대 1000입니다. 여기서 N=1000이 되는데, 찾아보니 1000 팩토리얼은 10의 2500제곱보다도 큰 수라고 합니다. 그러니까 그런 식으로 간단하게 풀 수 있는 문제는 아니라는 것을 알 수 있습니다.

다시 말하면 이 방법은 답은 구하기는 구하겠지만 너무 많은 연산을 필요로 하기 때문에 제한시간 안에 문제를 풀 수 없다는 한계가 있습니다.

가정2)

정렬을 이용하면 어떨까요.

대놓고 말하자면 줄 세워 놓고 비슷한 위치에 있는 사람을 짝지으면 편하지 않겠냐는 것입니다.

남자나 여자들을 오름차순이던 내림차순이던 그 값 순서대로 나열해 보면 값이 비슷한 사람들은 비슷한 위치에 오게 됩니다. 그러니까 성격순으로 정렬한 경우에는 남녀 각각이 최대한 자신과 비슷한 위치에 있는 상대를 찾을 때 가장 성격이 비슷한 사람을 만나게 될 것입니다. 즉 배우자를 선택할 때에 위치를 기준으로 할 수 있고 비슷한 위치의 배우자 후보가 우선시됩니다.

(우와... 진짜 속물이네요. 결혼시장 등급표인가요...)

또 이렇게 (정렬이) 된다면 모든 경우의 수를 따질 필요가 없습니다.

왜냐하면 전체 커플의 성격차이의 합이 최소가 되도록 하는 완벽한 매칭이 성사되었다고 할 때, 잘 맺어진 어떤 한 커플의 앞에 있는 다른 후보들은 반드시 정렬된 순서대로 그 커플의 앞에서 배우자를 찾아야만 하고, 마찬가지로 그 커플의 뒤에 있는 후보들은 그 커플의 뒤에서밖에는 배우자를 찾을 수 없기 때문입니다.

말로 하니까 이상한데 그려서 예시를 보면 쉽게 이해할 수 있습니다.

정렬된 선형 구조를 통해서 전체 커플의 성격 차이의 합이 최소가 되도록 하기 위한 매칭을 하려고 합니다.

위 그림처럼 연결선이 나란한 매칭은 가능합니다. 아무런 문제가 없습니다.

하지만 빨간 화살표처럼 연결선이 교차하는 모양으로 짝지어질 수는 없습니다.

그러니까 남자 a가 여자 B와 매칭되었다면, 남자 a의 오른쪽에 있는 남자 b는, 남자 a의 배우자인 여자 B의 오른쪽에 있는 여자 C나 D밖에 만날 수 없습니다.

'알 수 없는 방법으로 수치화된 성격'이 사람의 나이(연령)라고 한다면, 반드시 형수님보다는 나이가 어리거나 같은 여자와 교제해야 하고, 제수씨보다는 나이가 많거나 같은 여자를 만나야 한다는 규칙이 있다고 할 수 있습니다.

이로써 연산 횟수를 크게 줄일 수 있습니다.

이쯤 되면 배열을 맨 왼쪽에서 오른쪽까지 순서대로 훑으면서 차례로 커플을 만들면 어떨까 하는 데까지 생각이 미칩니다. 그러면 후보들을 정렬된 순서대로 하나씩 순회하며 짝을 찾아 주는 과정에서 한 커플이 맺어졌을 때 그 뒤에 있는 다른 후보들은 그 이전 연번까지의 후보들을 고려할 필요가 없을 것입니다.

가정3)

정렬을 하면 좋다는 것을 알았으니 완전탐색을 시도할 것입니다.

문제를 풀 때 보통 제일 쉬운 방법부터 써 보려고 하기 때문에 자연스럽게 그리디 알고리즘을 생각하게 됩니다.

선형 구조를 하나씩 한 번씩 순서대로 순회하는 것만으로 충분하다고 가정합니다.

제일 성격차 작은 사람, 일명 이상형을 찾아서 맺어 주고 그 다음으로 넘어가고 하는 식으로 풀 수 있을 것 같습니다.

남녀 그룹의 크기가 서로 다를 수 있고 최대한 많은 남녀를 짝지어야 하기 때문에 커플의 수는 항상 둘 중 크기가 작은 그룹의 인원수와 같다고 설정합니다.

여기서 편의상 크기가 작은 그룹을 구혼자 그룹, 크기가 큰 그룹을 후보자 그룹이라고 부릅니다.

이제 각각의 케미스트리를 측정하여 성격차가 최소가 되는 커플을 찾고 결혼시킬 것입니다.

풀이를 코드로 작성하면 다음과 같습니다.

public static int calc(int[] arrSmall, int[] arrBig) { // 인자: 구혼자, 후보자
	int[] spouse = new int[arrSmall.length]; // 찾은 배우자(이상형)
	int sum = 0; // 전체 커플의 성격 차이의 합
	for (int iSuitor = 0; iSuitor < arrSmall.length; ++iSuitor) { // 모든 구혼자는...
		int iIdeal = -1; // 이상형
		int minChem = Integer.MAX_VALUE; // 성격차이
		
		final int start = (iSuitor == 0)?0:(spouse[iSuitor - 1] + 1); // 연결선이 교차하지 않도록
		for (int iCandidate = start; iCandidate < arrBig.length; ++iCandidate) {
			int chem = Math.abs(arrSmall[iSuitor] - arrBig[iCandidate]); // 궁합 측정
			if (chem < minChem) { // 궁합 측정 결과 이상형 찾음
				minChem = chem;
				iIdeal = iCandidate;
			}
		}
		
		spouse[iSuitor] = iIdeal;
		sum += minChem;
	}
	return sum;
}

이대로 제출했더니 틀렸다네요.

반례가 있는데 가령 남녀의 성격값이 아래와 같은 상황을 가정한다면,

구혼자 2 3 4

후보자 1 2 3 100

상기한 풀이에서 구혼자의 선택은 시험 답안을 밀려 쓰듯이 {1, 2, 3}이 아닌 {2, 3, 100}이 됩니다.

탐욕 알고리즘의 결과는 소탐대실입니다.

가정4)

선형으로 쭉 훑어서 푸는 문제가 아닌 것 같기 때문에 재귀로 구현합니다.

재귀 함수로 완전 탐색을 구현할 때 인자로 컬렉션과 컬렉션의 인덱스가 들어가는데요.

그 인덱스를 주의 깊게 보면 답이 나온다고 합니다. ㄷㄷ

구혼자 0 1

후보자 0 1 2 3

위 같은 경우를 예로 들면 그림이 다음처럼 그려집니다.

이런 문제에서 자주 쓰는 Math.min()으로 점화식을 구성하여 DFS로 모든 경우를 순회하고 최소합을 구할 수 있을 것입니다.

중복되는 부분을 메모로 처리(메모이제이션)하면 대략적인 연산의 수는 비관적인 경우 1000 * 1000 = 1,000,000 정도입니다. 수행시간은 그렇게 해서 괜찮은 수준일 것 같습니다.

결국 다이나믹으로 풀게 되었습니다.

import java.io.*;
import java.util.*;

public class Main {

	public static int marryMe(final int indexSmall, final int indexBig) {
		if (indexSmall >= arrSmall.length) {
			return 0; // 모두 결혼함
		}
		if (indexBig >= arrBig.length) {
			return MAX_VALUE_OF_POSITIVE_NUMBER; // 여자를 기다리다가 결혼 못해서 노총각됨
		}
		if (memo[indexSmall][indexBig] != MAX_VALUE_OF_POSITIVE_NUMBER) {
			return memo[indexSmall][indexBig];
		}
		// 1. 이 여자랑 결혼하는 것이 사회 전체 편익의 증진에 유익하지 않다면
		memo[indexSmall][indexBig] = Math.abs(arrSmall[indexSmall] - arrBig[indexBig]) + marryMe(indexSmall + 1, indexBig + 1);
		// 2. 이 여자를 차고 다른 여자를 찾는 것이 최선이다
		memo[indexSmall][indexBig] = Math.min(memo[indexSmall][indexBig], marryMe(indexSmall, indexBig + 1));
		return memo[indexSmall][indexBig];
	}
	
	public static int[][] memo;
	public static int[] arrSmall, arrBig;
	public static final int MAX_VALUE_OF_POSITIVE_NUMBER = 100_000_000;
	
	public static void main(String[] args) throws IOException {
		final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final StringTokenizer st = new StringTokenizer(br.readLine());
		final int nMale = Integer.parseInt(st.nextToken());
		final int nFemale = Integer.parseInt(st.nextToken());
		
		final StringTokenizer stMale = new StringTokenizer(br.readLine());
		final int[] males = new int[nMale];
		for (int i = 0; i < nMale; ++i) {
			males[i] = Integer.parseInt(stMale.nextToken());
		}
		Arrays.sort(males);
		
		final StringTokenizer stFemale = new StringTokenizer(br.readLine());
		final int[] females = new int[nFemale];
		for (int i = 0; i < nFemale; ++i) {
			females[i] = Integer.parseInt(stFemale.nextToken());
		}
		Arrays.sort(females);
		
		// ---------------------------------------------------------------------------
		
		if (males.length <= females.length) {
			arrSmall = males;
			arrBig = females;
		} else {
			arrSmall = females;
			arrBig = males;
		}
		
		memo = new int[arrSmall.length][arrBig.length];
		for (int i = 0; i < memo.length; ++i) {
			for (int j = 0; j < memo[0].length; ++j) {
				memo[i][j] = MAX_VALUE_OF_POSITIVE_NUMBER;
			}
		}
//		for (int i = 0; i < memo.length; ++i) {
//			for (int j = 0; j < memo[0].length; ++j) {
//				System.out.print(memo[i][j]);
//			}
//			System.out.println();
//		}
		
		// ---------------------------------------------------------------------------
		
		System.out.println(marryMe(0, 0));
	}
	
} // public class

그런데 위처럼 구현해서 제출했더니 자바라서 그런지 시간 초과가 납니다.

C++에게는 무리가 없겠지만 느긋한 자바충은 더욱 견고한 알고리즘이 필요합니다.

(현재 맞은 사람 306명 중 자바 이용자는 28명뿐이더군요.)

연산을 줄이기 위해서 이것저것 건드려 보다가 두 번째 재귀 호출에 조건을 하나 걸었습니다.

import java.io.*;
import java.util.*;

public class Main {

	public static int marryMe(final int indexSmall, final int indexBig) {
		if (indexSmall >= arrSmall.length) { // 종료 조건: 모두 결혼함
			return 0;
		}
		if (memo[indexSmall][indexBig] != MAX_VALUE_OF_POSITIVE_NUMBER) { // DP
			return memo[indexSmall][indexBig];
		}
		
		// 1. 이 여자랑 결혼하는 것이 사회 전체 편익의 증진에 유익할까?
		memo[indexSmall][indexBig] = Math.abs(arrSmall[indexSmall] - arrBig[indexBig]) + marryMe(indexSmall + 1, indexBig + 1);
		//System.out.println(memo[indexSmall][indexBig]); // debug
		
		// 2. 아니면 이 여자를 차고 다른 여자를 찾아볼까?
		if (arrSmall.length - indexSmall < arrBig.length - indexBig) { // 그런 짓을 하려면 만날 수 있는 다른 여자가 더 남아 있어야 한다.
			memo[indexSmall][indexBig] = Math.min(memo[indexSmall][indexBig], marryMe(indexSmall, indexBig + 1));
		}
		
		return memo[indexSmall][indexBig];
	}
	
	public static int[][] memo;
	public static int[] arrSmall, arrBig;
	public static final int MAX_VALUE_OF_POSITIVE_NUMBER = 100_000_000;
	
	public static void main(String[] args) throws IOException {
		final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final StringTokenizer st = new StringTokenizer(br.readLine());
		final int nMale = Integer.parseInt(st.nextToken());
		final int nFemale = Integer.parseInt(st.nextToken());
		
		final StringTokenizer stMale = new StringTokenizer(br.readLine());
		final int[] males = new int[nMale];
		for (int i = 0; i < nMale; ++i) {
			males[i] = Integer.parseInt(stMale.nextToken());
		}
		
		final StringTokenizer stFemale = new StringTokenizer(br.readLine());
		final int[] females = new int[nFemale];
		for (int i = 0; i < nFemale; ++i) {
			females[i] = Integer.parseInt(stFemale.nextToken());
		}
		
		// ---------------------------------------------------------------------------
		
		if (males.length <= females.length) {
			arrSmall = males;
			arrBig = females;
		} else {
			arrSmall = females;
			arrBig = males;
		}
		Arrays.sort(arrSmall);
		Arrays.sort(arrBig);
		memo = new int[arrSmall.length][arrBig.length];
		for (int i = 0; i < memo.length; ++i) {
			for (int j = 0; j < memo[0].length; ++j) {
				memo[i][j] = MAX_VALUE_OF_POSITIVE_NUMBER;
			}
		}
		
		// ---------------------------------------------------------------------------
		
		System.out.println(marryMe(0, 0));
	}
	
} // public class

그렇게 해서 성공적으로 문제를 풀었습니다.

1. https://www.acmicpc.net/problem/1727 [본문으로]