정산 시스템에서 1원이 사라지는 문제 — Largest Remainder Method

구독료 천만 원을 시청 시간 비율로 세 CP에게 나눠준다고 하자. 비율대로 곱하고 원 단위로 반올림하면 이런 일이 생긴다.

CP A: 3,333,333.33... → 3,333,333
CP B: 3,333,333.33... → 3,333,333
CP C: 3,333,333.33... → 3,333,333
합계: 9,999,999  (1원 증발)

정산에서 "배분 합계 = 원본 금액"은 깨지면 안 되는 불변식이다. 1원이라도 어긋나면 회계가 안 맞는다.

Largest Remainder Method

선거 의석 배분에도 쓰는 고전적인 방법이다.

1. 각자 몫을 내림(floor) 으로 확정한다
2. 남은 금액(잔여)을 계산한다
3. 소수점 나머지가 큰 순서대로 1원씩 더 준다

public List<BigDecimal> distribute(BigDecimal pool, List<BigDecimal> weights) {
    BigDecimal total = weights.stream().reduce(ZERO, BigDecimal::add);
    var shares = weights.stream()
        .map(w -> pool.multiply(w).divide(total, 10, RoundingMode.DOWN))
        .toList();
    var floors = shares.stream().map(s -> s.setScale(0, RoundingMode.DOWN)).toList();

    long remainder = pool.subtract(floors.stream().reduce(ZERO, BigDecimal::add)).longValue();

    // 나머지 큰 순으로 1원씩
    var order = IntStream.range(0, shares.size()).boxed()
        .sorted(comparing(i -> shares.get(i).remainder(ONE), reverseOrder()))
        .toList();
    var result = new ArrayList<>(floors);
    for (int k = 0; k < remainder; k++) {
        int i = order.get(k);
        result.set(i, result.get(i).add(ONE));
    }
     result;
}