C++의 물과 주전자 문제

x 및 y 리터의 용량을 가진 두 개의 주전자가 있다고 가정합니다. 우리에게 제공되는 물의 양은 무한합니다. 이제 이 두 용기를 사용하여 정확히 z리터를 측정할 수 있는지 여부를 결정해야 합니다. z리터의 물을 측정할 수 있는 경우 끝까지 하나 또는 두 양동이에 z리터의 물이 들어 있어야 합니다.

우리는 다음과 같은 몇 가지 작업을 수행할 수 있습니다. −

• 모든 용기에 물을 완전히 채웁니다.

• 용기를 비우십시오.

• 다른 용기가 완전히 차거나 첫 번째 용기가 비워질 때까지 한 용기의 물을 다른 용기에 붓습니다.

따라서 x =2, y =5, z =4이면 true를 반환합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• x + y

• x =z 또는 y =z 또는 x + y =z이면 true를 반환합니다.

• 반환 true z는 x와 y의 gcd로 나눌 수 있고, 그렇지 않으면 false

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h&g;
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