Day15

오늘 할 일

• 해커랭크 난이도 쉬움 과제 다 풀기 (O)
• 해커랭크 난이도 중 문제 하나 풀어보기 (O) - 프로그래머스로 대체

공부한 문제

둘이 만날 수 있는가?

• 문제 링크
• 출발지점이 서로 다른 둘이 각각 a와 b의 이동거리를 가지고 있다고 할 때, 둘은 서로 겹치는 지점이 생기는가?

해법

둘의 이동속도 a와 b의 최대공약수가 n이라고 할 때 a의 배수와 b의 배수의 차이는 n이상으로 무한히 가능하다. 단 절대 최대공약수인 n미만이 될 수 없다. 따라서 둘의 출발지점의 차이가 속도의 최대공약수인 n보다 작다면 이 둘은 절대 만날 수 없다.
출발지점의 차이 % 속도의 최대공약수 != 0 이면 만날 수 없다.

최대공약수 구하기

• 유클리드 호제법
  MOD(modulo)연산(=나머지 연산)을 이용하여 최대공약수를 구하는 방식이다.

간단히 요약하면 최대 공약수를 구하고자 하는 두 수를 가지고 나머지가 0이 될 때까지 반복 연산했을 때 마지막으로 나눈 수가 둘의 최대 공약수이다.

속도 a의 값이 237, 속도 b의 값이 27이라고 하자.
237 % 27 == 21이다. 그럼 다시,
27 % 21 == 6. 다시
21 % 6 == 3. 마지막으로
6 % 3 == 0.
나머지가 0이 될 때 마지막으로 나눈 3이 최대공약수이다.

문제로 돌아와서, 만약 서로 떨어진 지점에서 출발하는 둘의 출발지점의 거리차가 3이상이라면 이 둘은 무조건 만날 수 있다. 하지만 거리차가 3미만이라면 둘은 평생 만나지 못한다.

• 하지만 링크의 캥거루 문제는 아래와 같은 제약 조건이 있어서 조금 다르게 풀어야 했음..
  The second kangaroo has a starting location that is ahead (further to the right) of the first kangaroo's starting location (i.e., x2 > x1). Because the second kangaroo moves at a faster rate (meaning v2 > v1) and is already ahead of the first kangaroo, the first kangaroo will never be able to catch up. Thus, we print NO.

=> 출발지점의 차이 % Math.abs(둘의 이동속도 차이) == 0 이면 만날 수 있다

참고

• 약수 구하기 & 최소공배수 & 최대공약수