문제 소개
용량이 각각 x리터와 y리터인 두 개의 물통이 있다고 가정해 보겠습니다. 우리는 무한한 양의 물을 사용할 수 있으며, 이 두 물통만으로 정확히 z리터의 물을 측정할 수 있는지 판단해야 합니다.
측정이 가능하려면, 작업이 끝난 시점에 한쪽 또는 양쪽 물통에 담긴 물의 총량이 정확히 z리터가 되어야 합니다.
허용되는 연산
이 문제에서 수행할 수 있는 연산은 다음 세 가지뿐입니다.
- 아무 물통이든 가득 찰 때까지 물을 채운다.
- 아무 물통이든 완전히 비운다.
- 한 물통에서 다른 물통으로 물을 붓는데, 받는 쪽 물통이 가득 차거나 붓는 쪽 물통이 빌 때까지 진행한다.
예를 들어 x = 2, y = 5, z = 4라고 하면, 결과는 true입니다. 실제로 5리터 물통을 가득 채운 뒤 2리터 물통에 옮겨 담고 비우는 과정을 반복하면 정확히 4리터를 만들 수 있습니다.
해결 접근 방법
이 문제는 베주 항등식(Bézout's Identity)을 활용하면 간단하게 해결할 수 있습니다. 베주 항등식에 따르면, ax + by = z를 만족하는 정수 a, b가 존재할 조건은 z가 x와 y의 최대공약수(gcd)의 배수라는 것입니다. 따라서 다음 순서로 판단합니다.
- x + y < z이면 false를 반환한다. (두 물통을 모두 채워도 z리터에 못 미치므로)
- x == z 또는 y == z 또는 x + y == z이면 true를 반환한다.
- z가 x와 y의 최대공약수로 나누어 떨어지면 true, 그렇지 않으면 false를 반환한다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if(x + y < z) return false;
if(x == z || y == z || x + y == z) return true;
return z % __gcd(x, y) == 0;
}
};
main(){
Solution ob;
cout << (ob.canMeasureWater(3,5,4));
}입력
3 5 4
출력
1
코드 설명
위 예제에서는 3리터와 5리터 물통으로 4리터를 측정하는 경우를 확인합니다. x + y = 8이므로 z = 4보다 크고, 3과 5의 최대공약수는 1이며, 4는 1로 나누어 떨어지기 때문에 결과로 1(true)이 출력됩니다. __gcd 함수는 C++에서 두 수의 최대공약수를 손쉽게 구할 수 있게 해주는 표준 라이브러리 함수입니다.