[Python] 1850 - 최대공약수 (실버1) : 유클리드 호제법

1. 문제 설명

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

1850번: 최대공약수

사실 나도 잊고 있었던 풀이법인데 다시 보니까 기억났다.

이래서 사람이 복습을 해야 돼

 

---

2. 아이디어

가장 처음에 떠오르는 무식한 방법은 a와 b값을 입력받고,

진짜 1111(4), 111(3)의 값을 저장하여 연산과정을 거치는 방법일 것이다.

문제를 어느정도 풀어보면 알겠지만, 이 방법은 절대 통과가 안 될 거라는 것을 짐작할 수 있다.

(지금 생각해보니까 4로 3을 나누고 비트 연산으로 값을 만들었다면 되지 않았을까..? ㅋㅋ)

 

이 당시의 나는 최대 공약수를 구하는 모든 방법을 찾아보다,

가장 빠른 유클리드 호제법을 택했던 것으로 기억한다.

그렇다면 유클리드 호제법이란 무엇인가?

 

---

유클리드 호제법

뭔가 있어보이지만 그리 어려운 내용은 아니다. 알고리즘이라기 보단 수학적 사고를 필요로 한다.

x, y의 최대 공약수는 y, r의 최대 공약수와 같다는 법칙을 응용한 코드이다. (r은 x를 y로 나눈 나머지 값)

r이 0이 나왔을 때, y의 값이 곧 최대공약수가 된다.

x를 a, y를 b라고 생각해보면 a에는 처음부터 b의 값을 할당하고, b에는 r의 값인 a%b를 할당시킨다.

그렇게 b(사실상 r)가 0보다 클 때까지 돌린다면 최종적으로 a가 최대 공약수가 될 것이다. 

---

3. 코드

def solution():
    a, b = map(int, input().split())

    while (b > 0): # 유클리드 호제법
        a, b = b, a % b
    print('1'*a)

solution()