728x90
2609번: 최대공약수와 최소공배수 (acmicpc.net)
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
브론즈인데도 어렵다고 느껴졌던 . ...
a, b = map(int, input().split())
tmp = 0
for i in range(min(a,b), 0, -1):
if a % i == 0 and b % i == 0:
tmp = int(i)
break
print(tmp)
print(tmp * (a // tmp) * (b // tmp))아이디어의 키포인트는 우선..
1.a랑 b중에 더 적은 값을 기준으로 계속 내려가면서 처음으로 두 값에 나머지가 0이 되는 값이 최대공약수가 된다
2.최대공약수는 더이상 서로 겹치는것으로 나눠지지 않는 공약수기때문에 각 a,b 를 최대공약수로 나눈것을 이에 곱해주면 바로 최소공배수가 됨.
728x90
'알고리즘 공부(C++)' 카테고리의 다른 글
| 백준 10816 숫자카드 2 - 딕셔너리 (0) | 2022.09.02 |
|---|---|
| 백준 1764 듣보잡 - 차집합 (0) | 2022.09.02 |
| 백준 18870 좌표 압축 - 정렬 (0) | 2022.08.31 |
| 백준 10610 30 그리디 (0) | 2022.08.30 |
| 백준 2606 바이러스 - DFS 그래프 순회 (0) | 2022.08.30 |