1037번: 약수
첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되
www.acmicpc.net
from math import gcd
N = int(input())
A = list(map(int, input().split()))
ans = A[0] * A[1] // gcd(A[0], A[1])
for i in range(2, N):
ans = ans * A[i] // gcd(ans, A[i])
#if ans in A:
# ans*=2
print(ans) 처음엔 최소공배수 문제라고 생각하고 위와 같이 풀었다가 틀렸다.
최소공배수라고 생각해서 최대공약수, 최소공배수에 대해 다시 한번 검색해보고 유클리드호제법에 대해 알게되었고, 파이썬에서 관련 라이브러리인 gcd 를 제공하는것도 알게되었다.
또 이과정에 N개의 최소공배수를 구하는 법에 대해서도 의도치 않게 알게되어 '답을 알게되었군..' 이라고 중얼거리며 위와 같이 구현했는데
아뿔싸.. 틀렸단다..
문제를 다시한번 자세히 읽어보니 A가 1과 N이 되어서는 안된다는 조건이 있어서 부랴부랴 구한 최소공배수가 input A 에 있는 경우 * 2를 해주는 로직을 넣고 제출했으나 또 틀렸다.
이때부터 뇌정지가 와서 결국 또 검색을 하고야 말았다... ㅠㅠ
[백준] 1037번 : 약수 in python 파이썬
파이썬으로 백준풀기 :: 1037번 약수 https://www.acmicpc.net/problem/1037 코드 1 2 input(); v = list(map(int, input().split())) print(min(v)*max(v)) cs 이 문제는 얼핏 최소공배수를 구하는 문제로..
leedakyeong.tistory.com
위 블로그 글을 참조하니 *2를 해주는게 왜 틀렸는지에 대해 나와있다.
결국 정답은 최솟값 * 최대값인데. 최솟값 과 최대값을 곱하면 왜 공배수가 되는지 좀 더 생각해봐야겠다.
from math import gcd
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = A[0] * A[-1]
print(ans)
ps. 문제에서 두번째 줄에 주어지는 값이 약수 라고 가정을 했으니 최소 최댓값을 구한게 N 이 아닌 최소공배수가 되는거구나..
역시 문제를 잘 읽어봐야...