[백준][Python] 2168번 타일 위의 대각선

2168번: 타일 위의 대각선

 

 

코드

def gcd(x,y):
	if y > x:
		x,y = y,x
	while 1:
		if y == 0:
			break
		x,y = y, x%y
	return x

x,y = map(int,input().split())
g = gcd(x,y)
print(x+y-g)

 

설명

예전에 비슷한 문제를 풀어봐서 답을 구하는 식이 x + y - gcd(x,y) 였던 것이 생각났다.

def gcd(x, y):
    for i in range(min(x, y), 0, -1):
        if x % i == 0 and y % i == 0:
            return i

처음에 최대공약수를 이런 식으로 구했더니 시간초과가 나서 유클리드 호제법을 사용했다.