[백준] #2168 타일 위의 대각선 python

https://www.acmicpc.net/problem/2168

2168번: 타일 위의 대각선

 

📕 설명 📕

 

유클리드 호제법.

 

대각선이 지나는 점의 개수는 x, y의 최대공약수임을 그림 그려서 알아냈다.

 

그리고 대각선이꼭지점을 지나가는 사각형은 x + y - 1

 

지나가지 않는 사각형은 x + y -1 -(점의 개수)

 

그래서,

 

x + y - gcd(x, y) 라는 식을 구할 수 있다.

🧑🏻‍💻 나의 풀이 🧑🏻‍💻

 

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)


x, y = map(int, input().split())
x, y = max(x, y), min(x, y)

result = x + y - gcd(x, y)
print(result)