Problem
https://www.acmicpc.net/problem/2609
Solution
code1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 최대공약수
def gcd(a,b):
for i in range(min(a,b), 0, -1):
if a % i == 0 and b % i == 0:
return i
# 최소공배수
def lcm(a,b):
for i in range(max(a,b), a*b+1):
if i % a == 0 and i % b == 0:
return i
a, b = map(int, input().split())
print(gcd(a, b))
print(lcm(a, b))
위 코드도 정답이 되긴 하지만 계산과정이 조금 비효율적이다. 아래의 방법은 유클리드 호제법과 최소공배수의 성질을 활용하여 시간을 단축하였다.
code2 (유클리드 호제법)
1
2
3
4
5
6
7
8
9
10
11
12
# 최대공약수
def gcd(a, b):
while b:
r = a%b
(a, b) = (b, r)
return abs(a)
a, b = map(int, input().split())
x = gcd(a, b)
y = int(a*b/x) # 최소공배수
print(x)
print(y)
Memo
위의 코드에서 최대공약수를 구하는 부분은 유클리드 호제법을 활용한 방법으로 나머지가 0이 될 때의 값을 찾는 것이다.
최소공배수는 최대공약수를 이용해서 구했는데 최소공배수 = 두수의 곱/최대공약수인 수의 성질을 활용한 것이다.