[Hacker Rank] Number Line Jumps (Easy) C++ 풀이

문제 링크

https://www.hackerrank.com/challenges/kangaroo/problem

분류

구현, 수학

시도한 방법

문제의 설명은 굉장히 구체적이지만, 간단하게 생각하면 일차함수의 접점 유무 판별과 같다.

두 캥거루는 각각 일차식 그래프가 되고, 속도는 기울기, 시작위치는 y절편과 같다.

예를 들어, 문제의 예시처럼 첫 경우를 가정해보면,

1번 캥거루는 2번 칸에서 출발해 매초 1칸씩 점프하고,
2번 캥거루는 1번 칸에서 출발해 매초 2칸씩 점프한다.

$$
Kangaroo_{1} = v_{1}x + x_{1}
$$

$$
Kangaroo_{2} = v_{2}x + x_{2}
$$

본 식에서 위 조건을 각각 대입하면, 아래와 같은 식을 얻을 수 있다.

$$
Kangaroo_{1} = x + 2
$$

$$
Kangaroo_{2} = 2x + 1
$$

그러므로, 두 직선이 x>=0 인 구간에서 정수 시간 단위로 측정하므로 접점의 x 좌표가 정수인지를 판별하는 방식으로 접근했다.
따라서, 위 두 식을 동치관계로 보아 판별식을 세우면 아래처럼 나타낼 수 있다.

$$
v_{1}x + x_{1} = v_{2}x + x_{2}
$$

$$
x = \frac{x_{2} - x_{1}}{v_{1} - v_{2}},
\quad x \in {,0,,1,,2,,\dots}
$$

위 식에서 두 직선의 기울기가 같은 경우(= 캥거루들의 속도가 같은 경우)를 처리해준 내용을 추가한 소스코드는 아래와 같다.
(기울기가 같고 절편이 같은 경우는 Test Case에 없는 것 같다. 처음엔 속도가 같으면 무조건 NO 로 처리했는데, 정답처리됐다.)

결과 코드

사족은 굉장히 복잡스러워 보이지만 코드는 정말 간단하다.

string kangaroo(int x1, int v1, int x2, int v2) {

    string answer = "NO";

    if(v1 == v2)
    {
        if(x1 == x2)
            return "YES";
        else
            return "NO";
    }

    double pos = static_cast<double>(x2 - x1) / (v1 - v2);
    if(pos >= 0 && (x2 - x1) % (v1 - v2) == 0)
        answer = "YES";

    return answer;
}