젓가락

아이디어

처음으로 든 생각은 젓가락 길이를 sorting 해서 서로 붙어있는 짝을 \(A,B\)로 두어야 할 것 같았다.

그 이후에는 이 쌍을 선택하거나 선택하지 않는 0-1 knapsack 문제와 다를 것이 없다.

증명

\(Claim\): 정답을 구성하는 쌍들 중 하나를 \(p\)라 하자 \(p = \{a, b, c\}(a \le b \le c)\)
크기 순서로 \(a\) 바로 뒤에 있는 원소 \(\bar{b}\)라 하면 \(\bar{b} = b\) 이다.

\(Proof\): 만약 \(a,b\)가 서로 크기상으로 한칸 이상 떨어져 있다고 가정하자.

점화식

\[points[i] = (chopsticks[i] - chopsticks[i + 1])^2\] \[DP[i][j] = \begin{cases} min\{DP[i + 1][j], DP[i + 2][j - 1] + points[i]\} & \text{if }j > 0 \\ DP[i + 1][j] & else \end{cases}\]

문제

사람들은 보통 식사를 할 때 젓가락을 두 개 사용한다. 그러나 모 선생님 댁에서는 조금 다르게 세 개의 젓가락을 사용한다. 우리가 일반적으로 사용하는 한 벌의 젓가락에 큰 젓가락을 한 개 더 포함시켜 큰 음식을 젓가락에 꽂아 먹는 방식을 택한다.

큰 젓가락의 경우에는 별도의 용도로 사용하기 때문에 문제가 없지만, 나머지 두 젓가락의 길이가 많이 차이 나는 경우에는 불편할 수도 있다. 한 사람이 가지게 되는 젓가락의 길이 A, B, C(A ≤ B ≤ C)라고 할 때, (A-B)×(A-B)가 그 벌점이 된다.

오늘은 모 선생님의 생일이라 K(1 ≤ K ≤ 1000)명의 사람들이 함께 식사를 하게 되었다. 이를 위해서 모 선생님은 K벌(3×K개)의 젓가락을 준비해야 한다. 이를 위해서 모 선생님은 이미 가지고 있는 N(3×K ≤ N ≤ 5000)개의 젓가락들 중에서 몇 개의 젓가락을 골라서 K명의 사람들에게 나눠주기로 하였다. 하지만 이렇게 많은 인원이 식사하게 된 경우가 처음이라 일부 젓가락의 길이가 맞지 않게 되었다. 모 선생님은 가급적 모든 사람들이 편하게 젓가락을 이용할 수 있도록, 각 사람에게 나눠준 젓가락의 벌점의 총 합이 최소가 되도록 하려 한다.

젓가락에 대한 정보가 주어졌을 때, 벌점의 총 합의 최솟값을 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 K, N이 주어진다. 다음 줄에는 N개의 젓가락의 길이가 주어진다. 각 젓가락의 길이는 1이상 32767이하의 정수이다.

출력

첫째 줄에 벌점의 총 합의 최솟값을 출력한다.

코드

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>

using namespace std;

const long long MAX_LENGTH = 32767; // == 2 ^ 15 - 1
const long long MAX_M = 1000 + 1, MAX_N = 5000 + 3, MAX = MAX_N * MAX_N * MAX_LENGTH;
int K, N, length, chopsticks[MAX_N], points[MAX_N];
long long dp[MAX_N][MAX_M];

//recursive version
//To use this function, dp array must be initialize to -1
long long memo(int i, int j) {
	//j: Number of pairs to pull out
	//i: current index
	//basis cases

	//check negative index or Insufficient nodes to pull out.
	if (j < 0 || i + j * 3 > N) return MAX;
	if (i == N - 1) return 0;

	long long& ret = dp[i][j];
	if (ret != -1) return ret;

	return ret = min(memo(i + 1, j), memo(i + 2, j - 1) + points[i]);
}


int main() {
	//init
	//Memset is a char array only initialization function
	//and sometimes does not work well in large arrays.
	for (int i = 0; i < MAX_N; i++) {
		for (int j = 0; j < MAX_N; j++) {
			dp[i][j] = MAX;
		}
	}

	//input
	cin >> K >> N;
	for (int i = 0; i < N; i++) {
		cin >> chopsticks[i];
	}

	//sorting chopsticks
	sort(chopsticks, chopsticks + N);

	//get points
	for (int i = 0; i < N - 1; i++) {
		int A = chopsticks[i], B = chopsticks[i + 1];
		points[i] = (A - B) * (A - B);
	}

	//dp
	//iteration version
	dp[N][0] = 0;
	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; i + j * 3 <= N && j <= K; j++) {
			if (j > 0) {
				dp[i][j] = min(dp[i + 1][j], dp[i + 2][j - 1] + points[i]);
			}
			else {
				dp[i][j] = dp[i + 1][j];
			}
		}
	}

	cout << dp[0][K] << endl;
}