[파이썬] 백준 1037 : 약수

[파이썬] 백준 1037 : 약수

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

1037번: 약수

실버 5

수학, 정수론

---

실버 상위 문제들 풀다 멘탈 나가서 힐링용으로 풀었는데 계속 틀려서 어이가 없었던 문제다.

당연히 최소공배수를 구하는 건줄 알고 입력 받은 값중 가장 큰 값에 2배를 한 후, 입력 받은 값들에 대해 나눴을 때 모든 모든 원소가 나누어 떨어진다면 최소공배수임으로 그것을 출력하도록 짰다.

import sys
input = sys.stdin.readline
N = int(input())
yak = list(map(int, input().split()))

maxx = max(yak) * 2
while True:
    for i in range(len(yak)):
        
        if maxx % yak[i] != 0:
            maxx *= 2
            break
    else:
        print(maxx)
        break

근데 예제를 잘 보니, 4와 2를 입력하면 8이 출력되도록 나와있다.

최소공배수를 구하는 문제라면 4와 2를 입력하면 4가 나오는 것이 맞다.

그렇다고 최소공배수가 포함되었을때 2를 곱한값을 출력하는 것도 아니다.

 

코드

import sys
input = sys.stdin.readline
N = int(input())
yak = list(map(int, input().split()))
minn = min(yak)
maxx = max(yak)
print(minn*maxx)

 

문제에서 요구하는 것은 약수의 성질을 이용한 풀이였던 것 같다.

입력받는 진짜 약수는 1과 자기 자신을 제외한 약수들이므로 그중 가장 작은값과 가장 큰 값을 곱하면 N을 구할 수 있다.

 

수학적인 사고가 잘 안되는 편이라 이 문제는 좀 납득하기가 어려웠다.