물통 문제(양 재기) 계산기
눈금 없는 통 두 개로 목표량을 재는 가장 짧은 절차를 찾아 줍니다. 3ℓ와 5ℓ로 4ℓ를 재는 다이하드 문제가 대표적이며, 잴 수 없는 경우에는 최대공약수를 근거로 왜 원리상 불가능한지도 함께 답합니다.
두 통 가운데 어느 쪽에 이 양이 남으면 성공입니다.
3ℓ 통과 5ℓ 통으로 4ℓ 재기
6번이면 됩니다
채우기·비우기·옮기기를 6번 하면 됩니다. 이보다 짧은 절차는 없습니다.
가장 짧은 절차
| 횟수 | 동작 | 3ℓ 통 | 5ℓ 통 |
|---|---|---|---|
| 0 | 둘 다 비어 있다 | 0 | 0 |
| 1 | 5ℓ 통을 가득 채운다 | 0 | 5 |
| 2 | 5ℓ 통 → 3ℓ 통으로 옮긴다 | 3 | 2 |
| 3 | 3ℓ 통을 비운다 | 0 | 2 |
| 4 | 5ℓ 통 → 3ℓ 통으로 옮긴다 | 2 | 0 |
| 5 | 5ℓ 통을 가득 채운다 | 2 | 5 |
| 6 | 5ℓ 통 → 3ℓ 통으로 옮긴다 | 3 | 4 |
상태를 (3ℓ 통에 든 양, 5ℓ 통에 든 양)으로 두면 모두 24가지뿐이고, 한 동작이 상태 사이를 잇는 길입니다. 너비 우선으로 훑으면 처음 닿은 경로가 곧 최소 횟수임이 보장됩니다.
계산 방법
- 1두 통의 용량을 넣습니다.
- 2재려는 양을 넣습니다.
- 3가능한지, 몇 번 만에 되는지 확인합니다.
- 4「가장 짧은 절차」 표에서 채우기·비우기·옮기기를 순서대로 따라갑니다.
- 5잴 수 없다고 나오면 최대공약수 설명을 읽어 왜 안 되는지 확인합니다.
자주 묻는 질문
여섯 번이면 됩니다. 5ℓ를 가득 채우고, 3ℓ로 옮겨 3ℓ 통을 채우고(5ℓ 통에 2ℓ가 남습니다), 3ℓ 통을 비우고, 남은 2ℓ를 3ℓ 통으로 옮기고, 5ℓ를 다시 가득 채운 뒤, 3ℓ 통이 찰 때까지(1ℓ만 더 들어갑니다) 옮기면 5ℓ 통에 정확히 4ℓ가 남습니다. 이보다 짧은 절차는 없습니다.
목표량이 두 통 용량의 최대공약수의 배수이고 큰 쪽 통의 용량 이하일 때만 잴 수 있습니다. 3과 5는 최대공약수가 1이라 1~5를 모두 잴 수 있지만, 4와 6은 최대공약수가 2라 홀수는 아무리 오래 부어도 잴 수 없습니다.
어떤 절차를 밟든 두 통에 든 물의 총량이 x×A + y×B(x, y는 정수) 꼴을 벗어나지 못하기 때문입니다. 채우기는 +A나 +B, 비우기는 −A나 −B이고, 옮기기는 두 통 사이에서만 오가므로 총량이 바뀌지 않습니다. 이런 꼴로 만들 수 있는 값이 최대공약수의 배수뿐이라는 것이 베주 항등식입니다.
상태를 (한 통에 든 양, 다른 통에 든 양)으로 두고 너비 우선으로 훑기 때문입니다. 상태가 (A+1)×(B+1)가지뿐이고 한 동작이 상태 사이를 잇는 길이라, 너비 우선 탐색에서 처음 닿은 경로가 곧 최소 횟수입니다.
있습니다. 「한쪽을 채워 다른 쪽에 붓고, 받는 쪽이 차면 비운다」를 되풀이하기만 해도 잴 수 있는 목표라면 반드시 닿습니다. 다만 어느 쪽부터 채우느냐에 따라 횟수가 다릅니다 — 3ℓ·5ℓ로 4ℓ를 재는 데 5ℓ부터 채우면 6번, 3ℓ부터 채우면 8번이 듭니다.
이 도구는 두 개까지만 다룹니다. 통이 셋이면 물을 버리지 않고 나누는 변형(예: 8·5·3으로 4씩 나누기)이 따로 있고, 상태 공간과 규칙이 달라 같은 판정이 그대로 적용되지 않습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 3ℓ·5ℓ로 4ℓ를 재는 다이하드 문제의 절차 여섯 걸음을 그대로 대조해 고정했습니다. 손으로 따라갈 수 있는 크기라 동작 하나하나와 통에 남는 양까지 확인했습니다.
- 판정(베주 항등식)과 탐색(너비 우선)을 따로 구현해 서로 대조합니다. 통 크기 20까지의 모든 조합, 모든 목표량에서 「최대공약수의 배수인가」와 「탐색이 절차를 찾았는가」가 어긋나지 않는 것을 확인했습니다. 원리가 전혀 다른 두 방법이라 서로를 검산해 줍니다.
- 최소 횟수라는 주장도 원리가 다른 두 번째 탐색(깊이를 하나씩 늘려 가며 훑는 방법)으로 다시 확인했습니다.
- 찾은 절차가 실제로 목표에 닿는지도 동작을 하나씩 되짚어 검사합니다. 통 크기 12까지의 모든 조합에서 표에 적힌 값과 실제 결과가 같은 것을 고정했습니다.
- 기계적인 두 방법(한쪽부터 채워 되풀이하기)이 잴 수 있는 목표라면 반드시 닿는다는 것, 그리고 최소 횟수보다 짧을 수는 없다는 것도 테스트로 고정했습니다.
- 불가능한 입력에는 이유를 나눠 답합니다. 최대공약수의 배수가 아닌 경우와 큰 쪽 통보다 많아 담을 데가 없는 경우는 다른 이야기이고, 「못 찾았다」고만 하면 반쪽입니다.
- 통은 300ℓ까지 다룹니다. 상태 수가 두 용량의 곱에 비례해 늘어나기 때문입니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.