[BOJ/수학] 백준 13011 - 사탕의 밀도 (Java)

13011 - 사탕의 밀도

https://www.acmicpc.net/problem/13011

문제

BOJ 알고리즘 캠프의 참가자 수는 N명이고, 0 ~ N - 1번까지 번호가 매겨져 있음
i번 참가자는 총 C[i] 리터의 사탕이 들어가는 바구니를 가지고 있고, 받고 싶은 사탕의 무게는 W[i] 그램
성원이는 모든 참가자들의 바구니를 가득 채워줄 것임(C[i] 리터만큼 모두 채울 것)
But, 사탕을 한 종류만 만들 수 있음(밀도 일정) -> 되도록 많은 참가자를 만족시키는 밀도를 선택해야 함

=> 최대한 많은 참가자 만족시키기 위해, 각 참가자의 W[i]와 실제로 받은 사탕의 무게 차이의 합 최소

입력
첫째 줄: 참가자 수 N (1 <= N <= 50)
둘째 줄: C[i] / 셋째 줄: W[i] (1 <= C[i], W[i] <= 1,000,000)
출력: 각 참가자의 W[i]와 실제로 받은 사탕의 무게의 차이의 합 최솟값
정답과 절대/상대 오차는 $10^{-9}$까지 허용

---

풀이

• 비용 함수 
  • 이상적 무게: `d * C[i]` (`d`: 밀도, `C[i]`: 부피)
  • 실제 무게: `W[i]`

public static double cost(double d) {
    double total = 0;
    for (int i = 0; i < N; i++) {
        total += Math.abs(d * C[i] - W[i]);
    }
    return total;
}

 

• 삼분 탐색 

double low = 0.0, high = 1e6;
for (int i = 0; i < 1000; i++) {
    double m1 = (2 * low + high) / 3;
    double m2 = (low + 2 * high) / 3;

    if (cost(m1) > cost(m2)) low = m1;
    else high = m2;
}

---

코드

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

public class boj_13011 {
    static int N;
    static double[] C, W;

    public static double cost(double d) {
        double total = 0;
        for (int i = 0; i < N; i++) {
            total += Math.abs(d * C[i] - W[i]);
        }
        return total;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        C = new double[N];
        W = new double[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            C[i] = Double.parseDouble(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            W[i] = Double.parseDouble(st.nextToken());
        }

        double low = 0.0, high = 1e6;
        for (int i = 0; i < 1000; i++) {
            double m1 = (2 * low + high) / 3;
            double m2 = (low + 2 * high) / 3;

            if (cost(m1) > cost(m2)) low = m1;
            else high = m2;
        }

        double d = (low + high) / 2;
        System.out.printf("%.9f\n", cost(d));
    }
}