[알고리즘] 백준 2824 파이썬 - 최대공약수

 

2824번: 최대공약수

 

문제

상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.

상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.

이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

 

 

문제풀이

import sys
input =sys.stdin.readline
#유클리드 호제법
def gcd(a,b):
    while b>0:
        a,b=b,a%b
    return str(a)[-9:]
#01
n=int(input().rstrip())
a=1
for i in list(map(int,input().split())):
    a*=i
#02
m=int(input().rstrip())
b=1
for j in list(map(int,input().split())):
    b*=j
#03
print(gcd(a,b))

- 유클리드 호제법을 사용하였다. (아래 링크를 참조)

 

[알고리즘] 백준 17087 파이썬 - 숨바꼭질6 (유클리드 호제법)

- #01 : n 길이만큼 입력받아 a에 모두 곱해준다.

- #02 : m 길이만큼 입력받아 b에 모두 곱해준다.

- #03 : 앞에서 구한 a,b를 통해 최대공약수를 구해준다.

           (최대공약수를 구하고 그 값을 마지막 9자리만 반환한다.

            여기서 int형은 인덱싱이 되지 않으므로, str 형태로 바꿔줘야 한다.)

            출력할 때 구한 값을 int형으로 변환하면 문제에서 틀렸다고 하니,

            str형태 그대로 출력해줘야 한다. 괜히 8분이나 시간 낭비했다.