백준 13011 (C++) 사탕의 밀도

최초 업로드: 2025-10-17 19:49:51

최근 수정 시간: 2025-10-17 19:49:51

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] 사탕의 밀도

[문제 링크](https://www.acmicpc.net/problem/13011)

## 문제 설명

BOJ 알고리즘 캠프의 스페셜 게스트 성원이는 캠프 참가자들에게 사탕을 만들어주려고 한다. BOJ 알고리즘 캠프의 참가자의 수는 N명이고, 0번부터 N-1번까지 번호가 매겨져 있다.

i번 참가자는 총 C[i] 리터의 사탕이 들어가는 바구니를 가지고 있고, 받고 싶은 사탕의 무게는 W[i] 그램이다.

성원이는 모든 참가자들의 바구니를 가득 채워줄 것이다 즉, C[i]리터만큼 모두 채울 것이다. 하지만, 성원이는 사탕을 한 종류만 만들 수 있다(밀도가 일정하다)

성원이는 되도록 많은 참가자를 만족시키는 밀도를 선택해야 한다. 최대한 많은 참가자를 만족시키게 하기 위해서, 각 참가자의 W[i]와 실제로 받은 사탕의 무게의 차이의 합을 최소로 하려고 한다.

각 참가자의 W[i]와 실제로 받은 사탕의 무게의 차이의 합을 최소로 하는 프로그램을 작성하시오.

## 입력

첫째 줄에 참가자의 수 N (1 ≤ N ≤ 50)이 주어진다.

둘째 줄에는 C[i], 셋째 줄에는 W[i]가 주어진다. (1 ≤ C[i], W[i] ≤ 1,000,000)

## 출력

각 참가자의 W[i]와 실제로 받은 사탕의 무게의 차이의 합을 최솟값을 출력한다. 정답과의 절대/상대 오차는 10-9 까지 허용한다.

## 풀이
차이의 최솟값은 등장한 값 중 하나로 구할 수 있다는 것이 잘 알려져 있습니다. 값이 최대 50개라 전부 살펴보면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long double ld;

ld c[50], w[50];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=0;i<n;i++) cin >> c[i];
 for(int i=0;i<n;i++) cin >> w[i];

ld minDiff=LONG_LONG_MAX;
 for(int i=0;i<n;i++) {
 ld g=w[i]/c[i], diff=0;
 for(int j=0;j<n;j++) diff += abs(w[j]-c[j]*g);
 minDiff = min(minDiff, diff);
 }
 cout << fixed << setprecision(9) << minDiff;
}
```