백준 2824 최대공약수

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/2824

• 첫 번째 줄 입력 : n
• 두 번쨰 줄 입력 : n개의 숫자만큼 입력
• 세 번째 줄 입력 : m
• 네 번째 줄 입력 : m개의 숫자만큼 입력
  
  

문제 : 두 번째 줄에 입력된 값들의 곱 a 와 네 번째 줄에 입력된 값들의 곱 b의 최대공약수 구하기

풀이

난이도 : Gold V

python에서 이 문제는 사실 문제에서 말하는 그대로 두 번째 줄의 값들을 모두 곱하고, 네 번째 줄의 값들을 모두 곱한 뒤에
math에 내장되어 있는 math.gcd(a, b)를 사용하면 바로 풀리는 문제이다.

✔ 하지만, 문제 의도에 맞추어 입력된 값들끼리 모두 비교하여 최대공약수를 구해주면서 구해진 최대공약수들끼리 곱하여 답을 구해주었다.

예)
a = [2, 3, 5]
b = [4, 5]

가 입력 되었을 때,
result = 1

1) a[0]인 2와 b[0]인 4의 gcd -> 2

2) 구한 gcd 값으로 비교했던 2와 4를 나누어줌
gcd = 2
a[0] = 2 // 2
b[0] = 4 // 2
result = 1 x 2
a = [1, 3, 5]
b = [2, 5]

3) 위 과정을 모든 값들에 대해서 iterative하게 반복한다.

✔ 또한, 최대공약수를 구할 때 '유클리드 호제법'을 이용하여 구해주었다.

• 유클리드 호제법 : a와 b의 최대공약수를 구하는 데 있어서 아래와 같은 방법으로 구할 수 있다.
  a % b = c
  b % c = d
  c % d = e
  ...
  만약 좌측값 % 우측값의 결과가 0이 나온다면 우측값이 a와 b의 최종적인 최대공약수이다.

  
  

  예) 20 와 30의 최대공약수 구하기

  20 % 30 = 20
  30 % 20 = 10
  20 % 10 = 0
  -> 최대공약수 : 10

코드

import sys
input = sys.stdin.readline

def gcd(a, b):
    while b > 0:
        tmp = a % b
        a = b
        b = tmp
    # 마지막에 modulo를 진행한 결과가 0이 나왔을 때, a에 b값을 넣어주고 끝나기 때문에 a를 return한다.
    return a

n = int(input())
list1 = list(map(int, input().split()))
m = int(input())
list2 = list(map(int, input().split()))

answer = 1
for i in range(len(list1)):
    for j in range(len(list2)):
        gcd_result = gcd(list1[i], list2[j])
        answer *= gcd_result
        list1[i] //= gcd_result
        list2[j] //= gcd_result

print(str(answer)[-9:])