[백준 2824번][실버 1] 최대공약수

자료구조를 제외한 라이브러리 최대한 사용하지 않고 문제풀기 (필요하면 직접 코딩)

문제

백준 2824 최대공약수

문제풀이 및 회고

문제의 의도에 맞게 해결했어야 하는데 문제의 의도를 무시하고 문제를 풀었다. 문제의 의도를 한번 파악하도록 하자. 잘못된 의도로 문제를 해결하다보면 제약조건이 많은 문제에 대해서는 틀리게 될거다.

풀이 1

그냥 모든 수 다 곱해서 바로 최대공약수를 구하는 방식으로 문제를 풀었는데 문제의 의도가 이게 아닌 거 같아서 한번 더 풀어보기로 했다.

import sys
input = sys.stdin.readline

N = int(input())
Ns = list(map(int, input().split()))
M = int(input())
Ms = list(map(int, input().split()))

def make_num(nums: list)->int:
    result = 1
    for num in nums:
        result *= num

    return result

A, B = make_num(Ns), make_num(Ms)

def gcd(A: int, B: int):
    if A < B:
        return gcd(B, A)
    if A == B:
        return A

    if A % B == 0:
        return B
    else:
        return gcd(A%B, B)

GCD_AB = str(gcd(A, B))
print(GCD_AB) if len(GCD_AB) <= 9 else print(GCD_AB[-9:])

풀이 2

DP랑 비슷하게 부분 문제 해결을 생각하면서 문제를 풀게 되었다. 모든 쌍의 최대공약수를 구해서 곱하면 전체의 최대공약수가 되는 식으로 문제를 풀었다.

import sys
input = sys.stdin.readline
#sys.stdin = open('baekjoon_2824.txt')

N = int(input())
Ns = list(map(int, input().split()))
M = int(input())
Ms = list(map(int, input().split()))

def gcd(A: int, B: int):
    if A < B:
        return gcd(B, A)
    if A == B:
        return A

    if A % B == 0:
        return B
    else:
        return gcd(A%B, B)


answer = 1
for i in range(N):
    for j in range(M):
        gcd_result = gcd(Ns[i], Ms[j])
        answer *= gcd_result
        Ns[i] //= gcd_result
        Ms[j] //= gcd_result

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