[백준] 1850 (실버1)

최대 공약수를 구하는 알고리즘을 작성하는 문제이다.
1학년 2학기에 C언어를 처음 배울 때, 재귀함수 부분에서 해당 알고리즘을 유클리드 호제니 뭐니 해서 배웠던 기억이 난다.
(그 때로 돌아가고 싶다..ㅎ)

하지만 우리는 파이썬의 math 라이브러리를 이용해서 간단하게 풀도록 하겠다.

import math
a,b = map(int,input().split())

print("1"*math.gcd(a,b))

유클리드 호제법

a>b인 두 수 a, b에 대해 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. (이 때, r은 a를 b로 나눈 나머지)
파이썬으로 간단하게 표현할 수 있다.

def gcd(a, b):
	while b:
    	a, b = b, a % b
    return a
    
# 재귀
def gcdV2(a, b):
	if b == 0:
    	return a
	else:
    	return gcdV2(b, a % b)