C++에서 포인트에 도달하기

<시간/>

시작점(sx, sy)과 목표점(tx, ty)이 있다고 가정하면 시작점에서 끝점까지 일련의 이동이 있는지 확인해야 합니다. 여기에서 이동은 점(x, y)을 가져 와서 (x, x+y) 또는 (x+y, y)로 변환하는 것으로 구성됩니다.

따라서 입력이 (1, 1) 및 (4,5)이면 답은 참이 됩니다. 이는 (1,1)을 (2,1), (3,1), (4)로 이동하기 때문입니다. ,1), 다음 (4,5).

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

tx> sx 및 ty> sy, do −
- tx> ty이면 -
  - tx :=tx 모드 ty
- 그렇지 않으면
  - ty :=ty 모드 tx
return(sx가 tx와 같을 때 참 AND sy <=ty AND (ty - sy) mod tx가 0과 같을 때) OR (sy가 ty와 같을 때 AND x>=sx AND (tx - sx) mod ty 0)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool reachingPoints(int sx, int sy, int tx, int ty) {
      while(tx > sx && ty > sy){
         if(tx > ty){
            tx %= ty;
         }else ty %= tx;
      }
      return (sx == tx && sy <= ty && (ty - sy) % tx == 0) || (sy == ty && tx >= sx && (tx - sx) % ty == 0);
   }
};
main(){
   Solution ob;
   cout << (ob.reachingPoints(1,1,4,5));
}

입력

C++에서 포인트에 도달하기

예시

입력

출력