[LeetCode] 780. Reaching Points

출처: leetcode.com/problems/reaching-points/

Reaching Points - LeetCode

문제

한번의 이동은 좌표 (x, y)에서 (x, x+y) 또는 (x+y, y)로의 변화로 구성된다.

 

시작 좌표 (sx, sy)와 목표 좌표 (tx, ty)가 주어지면, 좌표 (sx, sy)에서 (tx, ty)로 이동할 수 있다면 True를 반환한다. 그렇지 않다면 False를 반환한다.

 

단, sx, sy, tx, ty는 모두 [1, 10^9]의 범위를 갖는다.

예제

Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: True
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: False

Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: True

풀이

(sx, sy)에서 (tx, ty)로 어떻게 갈 수 있을까. 가장 단순한 방법은 아마도 (sx, sy)에서 이동 가능한 좌표들을 모두 확인해 보는 것이다. 즉, (sx+sy, sy)와 (sx, sx+sy) 좌표를 탐색하고 각 좌표에서 또 다시 다음 좌표을 탐색해가면서 (tx, ty)를 탐색해 가는 것이다. 문제는 한 지점마다 2개의 새로운 지점이 발생하니, 어림잡아 O(2n) 의 시간복잡도를 갖게 될 것이다. 실제로 이 풀이법으로 제출한 결과, TLE(Time Limit Exceeded)를 출력하였다.

 

이제 발상의 전환을 해보자. (sx, sy)에서 (tx, ty)를 찾는 이 문제를 거꾸로 (tx, ty)에서 (sx, sy)를 찾는 문제로 생각해보자.

 

(x, y) 좌표에서 한번의 이동을 통해 (x+y, y)로 이동했다고 가정해보자. 이 (x+y, y)좌표에서 역으로 (x, y)를 얻을 수 있을까. 당연히 얻을 수 있다. (x+y-y, y)를 통해서 얻을 수 있다. 그렇다면 일반적으로 (x, y)에서는 어떤 값을 빼고, 어떤 값을 유지 시켜야할까. 답은 x, y 둘 중에 더 큰 값에서 작은 값을 빼고, 작은 값은 그대로 유지시키면 된다.

 

이러한 이유는 최초 좌표인 sx, sy가 모두 1이상의 값이기 때문에 x+y > x, y의 관계가 성립하기 때문이다. 즉, 새로 만들어지는 x 혹은 y 좌표(=x + y)는 그대로 유지되는 값보다 무조건 큰 수가 된다. 이를 토대로 좌표 중 큰 수에서 작은 수를 빼는 것으로 이전 좌표를 쉽게 얻을 수 있다는 뜻이 된다.

i번 이동한 이후의 좌표: (x, y)

i-1번 이동했을 때의 좌표 추론
- 만약, x > y => (x-y, y)
- 만약, x < y => (x, y-x)

이를 코드로 표현하면 다음과 같다.

while (tx > sx || ty > sy) {
    if (ty > tx) {
        ty -= tx;
    } else {
        tx -= ty;
    }
}

여기서 한가지 최적화 포인트를 발견할 수 있는데, 만약 좌표의 이동이 한쪽 방향으로만 이루어진다면 (x, y)가 (x+y+y+...+y, y) 혹은 (x, y+x+x+...+x)로 이동한 것이다. 이를 위와 같이 뺄셈 연산으로 구하게 되면 이동한 횟수만큼 연산이 이뤄지게 되는데, 이를 한번에 구하기 위해서 나머지(%) 연산을 이용할 수 있다.

while (tx > sx || ty > sy) {
    if (ty > tx) {
        ty %= tx;
    } else {
        tx %= ty;
    }
}

위처럼 나머지 연산으로 바꾸게 되면 고려해야할 점이 하나 생긴다. 나머지 연산으로 변화하는 값이 필요 이상으로 작아지는 경우를 고려해야 한다.

(sx, sy) = (3, 4), (tx, ty) = (3, 10)

ty > tx, (3, 10 % 3) = (3, 1)

예제를 보면, 주어진 ty에서 tx를 두 번 빼는 것(10 - 6 = 4)으로 (sx, sy)에 도달할 수 있지만, 나머지 연산에서는 나머지인 1만 남긴채 모두 빼버린 결과를 만든다. 이를 방지하기 위해서 나머지 연산을 수행하기 전에 변화해야 하는 양을 계산하여 이용하도록 한다. 위의 예를 다시 한번 활용해서 이 말의 의미를 정확히 파악해보면 다음과 같다.

(sx, sy) = (3, 4), (tx, ty) = (3, 10)

1. ty > tx: ty의 값에 변화를 주어야 한다.
2. ty - sy: ty가 변화해야 하는 양을 계산 (10 - 4 = 6, tx를 이용해서 6만큼 뺄 수 있어야 함)
3. (ty - sy) % sx == 0 : tx를 이용해서 ty가 변화해야하는 양만큼 뺄 수 있는가? (6 % 3 == 0, 6만큼 빼는 것이 가능)

while (tx && ty && tx > sx || ty > sy) {
    if (sx == tx && (ty - sy) % tx == 0) return true
    if (sy == ty && (tx - sx) % ty == 0) return true

    if (ty > tx) {
        ty %= tx;
    } else {
        tx %= ty;
    }
}
return false

Github: 780.js

opwe37/Algorithm-Study