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

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

1850번: 최대공약수

# 최대 공약수 (재귀)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

처음에는 위와 같은 방식으로 최대 공약수를 구했으나 재귀적으로 최대 공약수를 구하기 때문에 메모리 초과가 났다.

따라서 아래와 같이 최대 공약수를 구하는 방법을 바꾸었고, 통과를 할 수 있었다.

 

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a  

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

print('1' * gcd(a, b))

상황에 따라 반복문으로 최대 공약수를 구할지 재귀로 구할지 판단하는 능력이 필요할 것 같다.