[백준] 1850번 : 최대공약수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1850번: 최대공약수

 

1. 문제 설명

2. 풀이과정

해당 문제에서 결과는 A와 B 길이의 최대공약수를 나타낸다.

즉, 3, 4의 최대공약수 1은 A(111)와 B(1111)의 최대공약수(1)의 길이로 나타내고

3, 6의 최대공약수 3은 A(111)와 B(111111)의 최대공약수(111)의 길이로 나타낸다.

위 규칙으로 해당 문제를 해결할 때는 최대공약수를 빠르게 계산할 수 있는 유클리드 호제법을 활용한다.

 

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘으로 큰 수를 작은 수로 나누는 MOD 연산을 수행하고 해당 단계에서의 작은 수와 MOD 연산의 결괏값(나머지)으로 MOD를 수행한다.

위 과정을 반복하다가 나머지가 0이 되는 과정의 작은 수를 최대공약수로 선택하는 방법이다.

 

슈도코드

1. A(A를 이루는 1의 개수), B(B를 이루는 1의 개수)
2. 최대공약수를 유클리드 호제법으로 구하는 함수 gcd(a, b):
   1. if (b가 0이면): a가 최대공약수
   2. else: gcd( b, a % b)
3. result(결괏값) = gcd(A, B)
4. 결괏값 크기만큼 1을 반복해서 출력

반응형

3. 소스코드

import sys

A, B = map(int, sys.stdin.readline().split())

def gcd(a, b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)
    
result = gcd(A, B)
print('1' * result)