[백준] 1850번 최대공약수 파이썬 Python / 유클리드 호제법 풀이

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

 

프로그래밍 알고리즘으로 최대공약수를 구하는 방법이

학교에서 배운 소인수 분해와 달라서 처음엔 이게 무슨 소린가 했다.

 

개념만 알면 MOD 연산으로 아주 쉽게 풀리는 문제였다.

 

유클리드 호제법 최대공약수에 대한 내용은 알고리즘 카테고리에서 자세히 다루겠다.

 

 

문제

 

 

 

풀이

 

입력 값들의 최대 공약수는 최대공약수 길이를 나타낸다.

예를 들어 3과 9의 최대공약수 3은 111, 111111111의 최대공약수 111의 길이이다.

 

 

코드

 

import sys
input = sys.stdin.readline

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

def gcd(x, y):
    if y == 0:      # y가 0이면 x가 최대공약수
        return x
    else:
        return gcd(y, x % y)    # 재귀로 구현

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

 

 

백준 1850번 최대공약수를 이해했다면 1934번 최소공배수 문제를 풀어보는 것을 추천한다.