[Python] 백준 1850번(최대공약수) 문제 풀이

 

def gcd(a, b):
    while b > 0:
        a, b = min(a, b), max(a, b)
        a, b = a, int(b%a)
    return a
    
a, b = list(map(int, input().split()))
print(gcd(int("1"*a), int("1"*b)))

 

 일단 이렇게 유클리드 알고리즘에 때려박아봤다. 메모리 초과가 떴다. 2^63까지 입력이 들어오기 때문에 당연한 결과다. "1"이 2^63번 반복된 문자열이 메모리 초과가 뜨지 않는 것이 이상하다. 아, 저 gcd 함수는 내가 만든 깃허브 repository 중 하나인 useful_defs의 Python 폴더의 gcd_EuclideanAlgorithm().py 파일에서 가져왔다(링크: https://github.com/kwonyonghyeon/useful_defs/blob/main/Python/gcd_EuclideanAlgorithm().py).

 

 그래서 내가 찾아봤다. 어떻게 해야 문제를 풀 수 있을까 찾아봤는데 다른 사람이 친절하게 올려둔 규칙성을 찾을 수 있었다.(링크: https://claude-u.tistory.com/404)그냥 입력받은 a와 b의 최대공약수만큼 1을 반복해서 출력하면 되는 문제였다. 왜 그런지 수학적으로는 모르겠다. 나중에 증명해보지 뭐.

 

def gcd(a, b):
    while b > 0:
        a, b = min(a, b), max(a, b)
        a, b = a, int(b%a)
    return a
    
a, b = list(map(int, input().split()))
print("1"*gcd(a, b))

 

 암튼 정답 코드는 이렇다. "1"을 a와 b의 GCD만큼 반복하여 출력한다.