C++에서 같은 점프 횟수 후 두 사람이 만나는지 확인하는 방법

이 문제에서는 두 사람의 시작 위치와 각자의 점프 거리를 나타내는 네 개의 정수가 주어집니다. 우리의 목표는 두 사람이 같은 점프 횟수를 반복한 뒤 서로 만나는 지점이 존재하는지 확인하는 것입니다.

문제 설명

p1 지점에서 출발하여 매번 j1만큼 점프하는 사람과, p2 지점에서 출발하여 매번 j2만큼 점프하는 사람이 있다고 가정합니다. 이때 두 사람이 경로상의 어떤 지점에서 만나게 되는지 판별해야 합니다.

예시를 통한 문제 이해

입력: p1 = 5, p2 = 9, j1 = 4, j2 = 2

출력: 만남 가능(Yes)

설명:

첫 번째 점프 후: p1 = 9, p2 = 11
두 번째 점프 후: p1 = 13, p2 = 13

두 번째 점프를 마친 후 두 사람 모두 위치 13에 도달하므로, 두 사람은 서로 만나게 됩니다.

해결 접근 방식

두 사람이 어떤 지점에서 만나려면 반드시 서로 다른 점프 거리를 가져야 합니다. 즉, 뒤처진 사람이 더 긴 거리를 점프해야 앞선 사람을 따라잡을 수 있습니다. 만남이 가능한지 판단하기 위해 다음 조건들을 검사합니다.

• p1 > p2인 경우, j1은 j2보다 작아야 합니다. (뒤에 있는 사람이 더 멀리 점프해야 따라잡을 수 있습니다)
• 그리고 ((p2 - p1) % (j1 - j2)) == 0 을 만족해야 합니다. (두 사람의 현재 위치 차이가 점프 거리 차이로 정확히 나누어 떨어져야 같은 시점에 같은 위치에 도달할 수 있습니다)

위 조건이 모두 충족되면 두 사람의 만남이 가능하고, 하나라도 충족되지 않으면 결코 만날 수 없습니다. 이 방법은 단순한 비교 연산과 나머지 연산만 사용하므로 O(1)의 시간 복잡도로 문제를 해결할 수 있습니다.

솔루션 구현 코드

#include<iostream>
using namespace std;

bool WillMeet(int p1, int j1, int p2, int j2){

    return ( (j1 > j2 && ( ((p2 - p1) % (j1 - j2)) == 0)) || (j2 > j1 && ( ((p1 - p2) % (j2 - j1)) == 0)) );
}

int main() {

    int p1 = 5, j1 = 4, p2 = 9, j2 = 2;
    if(WillMeet(p1, j1, p2, j2))
        cout<<"Both will meet at some point";
    else
        cout<<"Both will not meet at any point";

    return 0;
}

실행 결과

Both will meet at some point

주어진 입력값에서 WillMeet 함수가 true를 반환하므로, 프로그램은 "두 사람이 언젠가 만난다"는 메시지를 출력합니다. 실제로 두 번째 점프 이후 두 사람 모두 위치 13에서 만나는 것을 확인할 수 있습니다.