[Python/백준] #1850- [최대공약수]

[최대공약수]-1850번

1850번: 최대공약수

Another answer

import sys

a,b=map(int,sys.stdin.readline().split())
if(b>a): a,b=b,a
while(b!=0):
    a=a%b
    a,b=b,a
print(a*'1')

우선 이 문제는 그냥 최대공약수 문제가 아니었다. 입력받은숫자만큼의 1로 구성된 두 수의 최대공약수를 구하는 문제였는데, 처음에는 예제만 보고 두 1로구성된숫자들의 1의개수의 차이 즉 맨처음 입력받은 두 수의 차이만큼 1로 구성된 숫자가 답인줄 알았다. ex) 5랑 7이면 11111과 1111111이니까 11이 답인줄. 그런데 아니었다. 정확히 증명을 못하고 그냥 내가 임의로 숫자를 몇개 넣어보고 우연히 예제에 있는것들이 다 되서 이게 맞는줄 알고 계속 메모리 초과만 해결하려다가 못풀었다. 정답은 입력받은 두 수의 최대공약수만큼 1로 구성된 숫자가 답이었다 ㅜㅜ

정확한 증명을 찾아서 아래에 적어두겠다. 이렇게 문제 자체를 직관적으로 못풀고 증명하면서 풀어야되려면 수학적인 지식도 있어야하나 걱정이다. 증명은 백준의 jh05013님이 해주셨다.

Proof

x와 y의 최대공약수를 gcd(x, y)라고 하자.

입력받은 두 수를 a,b라 할때, 

"gcd((1이 a개), (1이 b개))는==(1이 gcd(a, b)개)이다"를 a+b에 대한 귀납법으로 증명할 수 있다.

a >= b일때, 

a=b인 경우에는 같은 수의 최대공약수이므로 자명하고, 이 경우는 base case인 a+b=2의 경우를 포함합니다. 따라서 base case를 증명했습니다.

이제 a+b=2, 3, ..., k까지 명제가 성립한다고 가정하고, a+b=k+1이라고 합시다.

x>y일 때 gcd(x, y) = gcd(x-y, y)라는 성질(유클리드 호제법)을 이용합니다. (1이 a개)에서 (1이 b개)를 빼면 (1이 a-b개, 0이 b개)가 됩니다. 즉 gcd((1이 a개), (1이 b개)) = gcd((1이 a-b개, 0이 b개), (1이 b개))입니다.

그 다음에는 p와 y가 서로소일 때 gcd(xp, y) = gcd(x, y)라는 성질을 이용합니다. 10의 거듭제곱은 (1이 b개)와 서로소이므로 gcd((1이 a-b개, 0이 b개), (1이 b개)) = gcd((1이 a-b개), (1이 b개))이고

귀납적 가정에 의해 gcd((1이 a-b개), (1이 b개)) = (1이 gcd(a-b, b)개)이다.

gcd(x, y) = gcd(x-y, y) 성질에 의해 (1이 gcd(a-b, b)개) = (1이 gcd(a, b)개)이다.