[백준] 2824 최대공약수 (파이썬 Python)

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

2824번: 최대공약수

문제 설명

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

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

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

---

풀이 과정

• 나의 풀이

① 최대공약수 구하는 법

  유클리드 호제법을 통해 최대공약수를 쉽게 구할 수 있다.

  유클리드 호제법이란 기원전 300년 전에 나온 가장 오래된 알고리즘으로 유명하다.

 

  유클리드 호제법으로 최대공약수를 구하는 방법은 다음과 같다.

○ 두 자연수 a,b에 대하여 a를 b로 나눈 나머지 r에 대해 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이를 계속 반복하며 b가 0이 될 때, a값이 바로 최대공약수이다. (재귀와 반복이 느껴진다..!!)

 

② 문제에 적용하기

# 2824 최대공약수
import sys
input = sys.stdin.readline

def gcd(a,b) :
    while b > 0 :
        tmp = a%b
        a = b
        b = tmp
    return a

def multiply(lst) :
    return eval('*'.join([str(n) for n in lst]))

N = int(input())
N_lst = list(map(int,input().split()))

M = int(input())
M_lst = list(map(int,input().split()))

a = multiply(N_lst)
b = multiply(M_lst)

print('%s'%str(gcd(a,b))[-9:])

  ①의 방법으로 gcd 함수를 만들어주었다.

  multiply 함수를 통해 둘째 줄과 넷째 줄 입력값을 모두 곱하여 변수 a,b에 저장한다.

  두 수의 최대공약수를 출력하는 과정에서 만약, 9자리보다 길다면, 마지막 9자리만 출력하기에 (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)  출력값을 제한해주었다.

 

+) 파이썬에서 리스트 안의 원소를 곱하는 방법 (아래 링크를 통해 확인 가능)

https://animoto1.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EB%B0%B0%EC%97%B4-%EC%95%88%EC%9D%98-%EC%9B%90%EC%86%8C%EC%9D%98-%EA%B3%B1%EC%9D%84-%EA%B5%AC%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95

 

---