[LeetCode] 858 | Mirror Reflection | Python

---

문제 링크: https://leetcode.com/problems/mirror-reflection/

---

문제

There is a special square room with mirrors on each of the four walls. Except for the southwest corner, there are receptors on each of the remaining corners, numbered 0, 1, and 2.

The square room has walls of length p and a laser ray from the southwest corner first meets the east wall at a distance q from the 0th receptor.

Given the two integers p and q, return the number of the receptor that the ray meets first.

The test cases are guaranteed so that the ray will meet a receptor eventually.

---

조건

• 1 <= q <= p <= 1000

---

내 풀이

위 그림처럼 p=6, q=4인 문제가 주어졌다고 생각해보자.

그럼 빛이 모서리에 닿기까지 반사되는 과정은 아래 그림과 같다.

주어진 사각형 방에 대해서 빛은 옆으로 두번, 위로 한번 반사될 것이다.

이 두번과 한번이 계산되는 방식은 다음과 같다.

4와 6의 최소공배수인 12(lcm)에 대해서 $4 \times (2+1) = 12$, $6 \times (1+1) = 12$

위로 한번 반사된다는 뜻은 위 그림처럼 이 사각형이 세로로 2개(h) 존재한다는 뜻이며,

옆으로 두번 반사된다는 뜻은 이 사각형이 가로로 3개(w) 존재한다는 뜻이다.

 

h가 2로 나눠진다면 빛의 종착점이 사각형의 아래쪽이 된다는 뜻이므로 항상 0을 리턴한다.

왜냐하면 문제에서 모든 빛은 0, 1, 2로만 간다고 했기 때문이다.

 

h가 2로 나눠떨어지지 않는다면 빛의 종착점이 사각형의 위쪽이 된다는 뜻이 되므로 1과 2중 선택해야 한다.

w가 2로 나눠떨어진다면 빛의 종착점은 사각형의 왼쪽이 되므로 2를 리턴, 2로 나눠떨어지지 않는다면 사각형의 오른쪽에서 끝나게 되므로 1을 리턴한다.

---

100%는 처음봐서 올리고싶었다 ㅎ

---

코드

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        def GCD(x, y):
            while y:
                x, y = y, x%y
            return x
        
        def LCM(x, y):
            return (x*y) // GCD(x, y)
        
        lcm = LCM(p, q)
        
        h = lcm // p
        w = lcm // q
        
        if h%2 == 0:
            return 0
        
        if w%2 == 0:
            return 2
        else:
            return 1