문제 소개
이 문제에서는 용량이 각각 x와 y인 두 개의 물통과 무한한 양의 물 공급원이 주어집니다. 목표는 한 물통에 정확히 1리터의 물을 담아내는 프로그램을 작성하는 것입니다. 단, x와 y가 서로소(co-prime)라는 조건이 전제됩니다.
서로소(Co-prime)란?
서로소는 '상대 소수(relatively prime)', '상호 소수(mutually prime)'라고도 불리며, 두 수 사이의 공약수가 1뿐인 관계를 말합니다. 즉, 두 수의 최대공약수(gcd, greatest common divisor)가 1이라는 의미입니다.
해결 접근 방법
용량이 x인 물통 V1과 용량이 y인 물통 V2가 있다고 가정해 보겠습니다. 두 물통으로 1리터를 측정하는 절차는 다음과 같습니다.
1. V1을 물 공급원으로 가득 채웁니다.
2. V1의 물을 V2에 붓습니다.
3. V2가 가득 차면 비우고, V1이 비면 다시 채웁니다.
4. 이 과정을 V1에 1리터의 물이 남을 때까지 반복합니다.
x와 y가 서로소이므로, 이 과정은 본질적으로 x의 배수를 y로 나눈 나머지((k·x) mod y)를 계산하는 것과 같으며, 베주 항등식(Bézout's identity)에 따라 반드시 1에 도달하게 됩니다.
예시
구체적인 예를 통해 살펴보겠습니다.
입력 −
V1 = 5, V2 = 8
V1 = 5 ; V2 = 0 -> V1의 물을 V2에 붓고 V1을 다시 채웁니다. V1 = 5 ; V2 = 5 -> V1의 물을 V2에 붓고 V1을 다시 채웁니다. V1 = 2 ; V2 = 0 -> V1의 물을 V2에 붓습니다. V2가 가득 찼으므로 비웁니다. V1 = 5 ; V2 = 2 -> V1의 물을 V2에 붓고 V1을 다시 채웁니다. V1 = 5 ; V2 = 7 -> V1의 물을 V2에 붓고 V1을 다시 채웁니다. V1 = 4 ; V2 = 0 -> V1의 물을 V2에 붓습니다. V2가 가득 찼으므로 비웁니다. V1 = 1 ; V2 = 0 -> V1의 물을 V2에 붓고 V1을 다시 채웁니다. 이 시점에서 V1은 1리터의 물을 측정했습니다.
예제 코드
위 해결 방법을 구현한 C++ 프로그램입니다.
#include <iostream>
using namespace std;
int x, y, V1, V2 = 0;
// V1에서 V2로 물을 옮기는 함수
int transferWater(int amt1, int amt2) {
if (amt1 + amt2 < y){ // V2에 모두 담을 수 있는 경우
V2 += V1;
return V1;
}
int transferred = y - V2; // V2가 가득 찰 때까지 옮길 수 있는 양
V2 = 0; // V2를 비움
return transferred;
}
// V1에 1리터가 남을 때까지 반복
void measure1Litre() {
while(V1 != 1){
if (V1 == 0)
V1 = x; // V1이 비면 다시 채움
cout<<"Vessel 1: "<<V1<<" | Vessel 2: "<<V2<<endl;
V1 = V1 - transferWater(V1, V2);
}
cout<<"Vessel 1: "<<V1<<" | Vessel 2: "<<V2<<endl;
}
int main() {
x= 5, y = 8;
measure1Litre();
return 0;
}출력 결과
Vessel 1: 5 | Vessel 2: 0 Vessel 1: 5 | Vessel 2: 5 Vessel 1: 2 | Vessel 2: 0 Vessel 1: 5 | Vessel 2: 2 Vessel 1: 5 | Vessel 2: 7 Vessel 1: 4 | Vessel 2: 0 Vessel 1: 5 | Vessel 2: 4 Vessel 1: 1 | Vessel 2: 0
마무리
이 알고리즘은 매 단계마다 V1을 채우고 V2에 붓는 단순한 동작만 반복하지만, 서로소 조건이 보장되어 있다면 최대 O(y)번의 반복 안에 반드시 V1에 1리터를 남기게 됩니다. 두 수가 서로소가 아닌 경우에는 1리터를 측정할 수 없으므로, 입력값의 최대공약수가 1인지 확인하는 전처리 과정을 추가하는 것도 좋은 방법입니다.