[백준] 26073 외로운 곰곰이는 친구가 있어요 (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/26073

26073번: 외로운 곰곰이는 친구가 있어요

 

 

작성코드

 

 

해설

 

1) 좌표에 도달하기 위한 시간 제한 같은것은 없기 때문에 얼마나 오랫동안 헤매던 상관없이 도달만 하면 된다.

즉, 좌표이동 값의 최소단위를 알면 도달 가능 여부를 알 수 있다.

(Ex. 이동 가능 거리가 9999와 9998이 있다면 오른쪽으로 9999 이동 후 왼쪽으로 9998을 이동한다면 오른쪽 1 이동이 가능, 해당 값은 정수 좌표계 어디든 도달가능하다)

 

 

2) 최소단위는 최대 공약수와 동일하다. 최대 공약수는 유클리드 호제법으로 구할 수 있다.

 

 

3) 유클리드 호제법

유클리드 호제법

2개의 자연수 a,b (a>b)에 대해서 a를 b로 나눈 나머지가 r일 때,

a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.

   

while(b != 0):

     r = a % b

     a = b

     b = r

a 가 최대 공약수가 된다.

 

4) 여러 수의 최대 공약수

두 수의 최대 공약수를 구하고 이 최대 공약수를 다른 수와 다시 계산하는 것을 반복하면 전체 수의 최대 공약수를 구할 수 있다.

for문을 돌면서 모든 수의 종합 최대공약수를 구한다.

 

 

5) 도달 가능 여부 출력

 

목표 위치가 0,0 이므로 최대 공약수가 좌표 X,Y 값을 나누어 둘 다 나머지가 0이라면 도착, 아니면 실패이다