BOJ 13011 - 사탕의 밀도

* BOJ 13011 - 사탕의 밀도

[분류 - 수학]

  굉장히 재밌는 문제.

  아래 수식을 생각해보자. 우리의 목표는 최종 비용을 최소하는 것이 목표다. 

  이는 곧 total cost를 최소화 하는 것임을 알 수 있다. 여기서 x를 곱한다고 한들 최소성에 대해 영향을 주지 않는다.

  또 하나의 값에 대해 Wi개로 나눠보자.

  하나가 아니라 모든 i에 대해 분해를 하고나면 |x-Ci/Wi| 형식으로 통일할 수 있다. 여전히 이 합을 최소화 하는 것이 문제에서 원하는 목표와 동치임을 계속 생각하고 있어야 합니다.

  

를 만족하는 x값을 x좌표에 찍어봅시다. 이제 이 합을 최소화하는 x의 위치를 특정해야 하는데 그 x의 위치가 정해지면 합은 찍었던 모든 x좌표와의 거리로 볼 수 있습니다.

  자 x가 찍힌 두 점 사이에 있다고 가정해봅시다(x가 찍은 점 위에 있지 않는 경우입니다). 이 때 이 x의 왼쪽에 있는 점의 개수 l과 오른쪽에 있는 점의 개수를 r이라고합시다 x 바로 왼쪽에 있는 찍힌 점을 지나치지 않을 정도의 양의 실수 a에 대해 x가 왼쪽으로 a만큼 이동했다고 가정해봅시다. l과 r의 값은 변하지 않습니다. 총합은 어떻게 될까요 ? 총합은 l과 r이 같다면 그대로일테고 아니라면 총합은 달라집니다. 즉 l > r인 경우 왼쪽으로 간다면 총합은 작아질테고, 반대라면 증가하겠죠. 이 값은 l과 r의 일차식으로 나타낼 수 있습니다.

  이처럼 두 점 사이에 x를 두는 것보다 x좌표에 찍었던 점 위에 두는 것이 언제나 최적입니다.

  이제 우리가 원하는 total cost를 최소로 하는 x값은 x좌표에 찍은 점들 중 하나입니다. 이제 단순히 브루트 포스로 답을 찾아주시면 되겠습니다~

#include<cstdio>
#include<cstdlib>
using namespace std;
int main() {
	int N, i, j, C[50], W[50];
	double ans = 1e18, t, c;
	scanf("%d", &N);
	for (i = 0; i < N; i++) scanf("%d", &C[i]);
	for (i = 0; i < N; i++) scanf("%d", &W[i]);
	for (i = 0; i < N; i++) {
		c = (double)C[i] / W[i];
		for (t = j = 0; j < N; j++)
			t += abs(W[j] - C[j] / c);
		ans = ans > t ? t : ans;
	}
	printf("%.11lf", ans);
	return 0;
}