[백준알고리즘] 1850번: 최대공약수 -Python

[백준알고리즘] 1850번: 최대공약수 -Python

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

1850번: 최대공약수

예제를 헷갈릴만하게 줬다. 처음에 보면 두 수의 차이만큼 1이 존재하는 것처럼 느껴진다. 하지만 뭔가 이상해서 생각해보니 두 수의 최대공약수만큼 1이 존재하는 것과 같았다.

 

두 수의 차이만큼 1이 존재하는 것이 아닌 것은 다음을 보면 알 수 있다. 입력으로 8 6 이 주어진 경우와 8 3 이 주어진 경우를 생각해보자.

 

8 6 이 주어진 경우에는 11111111, 111111의 최대공약수를 구해야 한다. 유클리드 호제법에 의해 다음과 같이 구할 수 있다.

gcd(11111111, 111111) = gcd(111111, 11) = gcd(11, 0) = 11

 

8 3 이 주어진 경우에는 마찬가지로 다음과 같이 구할 수 있다.

gcd(11111111, 111) = gcd(111, 11) = gcd(11, 1) = gcd(1, 0) = 1

 

8 3 의 경우에는 두 수의 차이인 5만큼의 11111이 아닌 1이 최대공약수임을 확인했다. 이 값들을 잘 생각해보면 주어진 크기들의 최대공약수만큼 1이 존재한다는 것을 알 수 있다.

 

8 6 이 주어진 경우 gcd(8, 6) = 2 인 만큼 11이 gcd가 되고, 8 3 이 주어진 경우 gcd(8, 3) = 1 인 만큼 1이 gcd가 된다.

 

지금보니 출력을 왜 굳이 저렇게 했는지 모르겠다. 문제를 풀다가 이끌려갔나..

import sys

N, M = map(int, sys.stdin.readline().split())
X, Y = (N, M) if N > M else (M, N)

while X%Y:
    X, Y = Y, X%Y

sys.stdout.write(''.join(['1']*Y))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다