송금 횟수를 최소로 줄이는 원리
1차는 민수가, 2차는 지영이가, 편의점은 도윤이가 냈다면 누가 누구에게 얼마를 보내야 할까요? 회차마다 따로 나누면 송금이 열 번 넘게 오가지만, 사람별로 "낸 돈과 부담할 돈의 차이"만 맞추면 훨씬 적은 송금으로 끝납니다. 딱정산이 송금표를 만드는 방식을 예시와 함께 설명합니다.
예시 — 다섯 명, 결제 네 번
| 회차 | 결제 | 금액 | 참여 |
|---|---|---|---|
| 1차 고깃집 | 민수 | 100,000원 | 5명 모두 |
| 2차 술집 | 지영 | 60,000원 | 민수 · 지영 · 현우 |
| 3차 노래방 | 수진 | 45,000원 | 지영 · 현우 · 수진 · 도윤 |
| 편의점 | 도윤 | 24,000원 | 민수 · 도윤 |
회차마다 "참여한 사람이 결제한 사람에게 1/n씩 보내기"로 하면 1차 4번, 2차 2번, 3차 3번, 편의점 1번으로 송금이 10번입니다. 같은 사람이 같은 사람에게 여러 번 보내기도 하고, 서로 주고받는 경우도 생깁니다.
1단계 — 사람별 차액 구하기
먼저 사람마다 실제로 낸 돈(결제)과 내야 할 돈(부담)을 모두 더합니다. 부담은 참여한 회차의 1/n을 합한 값입니다. 차액이 +면 돌려받을 사람, −면 보낼 사람입니다.
| 이름 | 낸 돈 | 부담 | 차액 |
|---|---|---|---|
| 민수 | 100,000 | 52,000 | +48,000 |
| 지영 | 60,000 | 51,250 | +8,750 |
| 현우 | 0 | 51,250 | −51,250 |
| 수진 | 45,000 | 31,250 | +13,750 |
| 도윤 | 24,000 | 43,250 | −19,250 |
차액을 모두 더하면 0이 됩니다. 누군가 더 낸 만큼 다른 누군가 덜 냈기 때문입니다. 이제 회차는 잊고, 이 차액만 0으로 만들면 됩니다.
2단계 — 차액을 맞추는 가장 적은 송금 찾기
차액이 있는 사람이 N명이면 송금은 많아야 N−1번이면 됩니다. 한 사람씩 차액을 0으로 만들어 가면 마지막 사람은 저절로 0이 되기 때문입니다. 위 예시는 다섯 명이니 최대 4번입니다.
여기서 더 줄일 수 있는 경우가 있습니다. 차액의 합이 0이 되는 작은 무리가 있다면, 그 무리끼리만 정산하고 끝낼 수 있습니다. 예를 들어 A가 +1만, B가 −1만, C가 +3만, D가 −3만이라면 "B→A", "D→C" 두 번이면 끝납니다(네 명인데 2번). 딱정산은 이런 무리를 최대한 많이 찾아 송금 횟수를 줄입니다. 18명까지는 가능한 무리를 모두 따져 정확히 최소를 찾고, 그보다 많으면 큰 금액부터 맞춰 가는 빠른 방법을 씁니다.
결과 — 송금 4번
| 보내는 사람 | 받는 사람 | 금액 |
|---|---|---|
| 현우 | 민수 | 48,000원 |
| 현우 | 수진 | 3,250원 |
| 도윤 | 수진 | 10,500원 |
| 도윤 | 지영 | 8,750원 |
10번이던 송금이 4번으로 줄었습니다. 받는 사람 입장에서도 민수는 한 번, 지영은 한 번, 수진은 두 번만 확인하면 됩니다.
송금 횟수가 같을 때 고르는 기준
최소 송금 방법이 여러 가지일 때는 다음 순서로 고릅니다.
- 한 사람이 여러 번 보내지 않게 — 보내는 횟수가 고르게 퍼진 쪽을 고릅니다.
- 결제를 안 한 사람이 먼저 보내게 — 이미 카드를 긁은 사람이 또 송금까지 하는 일을 줄입니다. 그래서 위 예시에서도 결제하지 않은 현우가 송금을 맡았습니다.
결과 화면은 보내는 사람별로 묶어 "현우 (총 51,250원) → 민수 48,000원, → 수진 3,250원"처럼 보여줍니다. 각자 자기 이름 아래만 보면 됩니다.
직접 계산해 보면
위 예시를 손으로 해 보면 왜 차액 방식이 편한지 알 수 있습니다. 회차마다 나누면 "민수에게 20,000원, 지영에게 20,000원, 수진에게 11,250원…"처럼 한 사람이 서너 번 송금해야 하고, 어떤 사람은 받기도 하고 보내기도 합니다. 차액 방식은 "결국 나는 얼마를 더 냈고 얼마를 덜 냈나" 하나만 보기 때문에, 보내는 사람은 보내기만, 받는 사람은 받기만 합니다.
차액이 0인 사람은 송금표에 나오지 않습니다. 낸 돈과 부담이 정확히 같다면 아무것도 하지 않아도 됩니다.
자주 묻는 질문
- 송금 횟수가 정말 최소인가요?
- 차액이 있는 사람이 18명까지는 차액의 합이 0이 되는 무리를 가능한 모든 조합으로 따져 정확한 최소 횟수를 찾습니다. 18명을 넘으면 계산량이 너무 커져서, 큰 금액부터 맞춰 가는 빠른 방법으로 대신합니다. 이때는 최소가 아닐 수 있지만 "차액이 있는 사람 수 − 1"번을 넘지 않습니다.
- 송금표 말고 다른 방식으로 보내도 되나요?
- 송금표는 "이렇게 보내면 가장 적게 보낸다"는 한 가지 방법입니다. 사람들끼리 합의해 다르게 보내도 되지만, 각자 받는 돈과 보내는 돈의 합이 차액과 같아야 정산이 맞습니다.