혀니의 이거저거 뿌시기

백준 2609 최소공배수 최대공약수 본문

알고리즘 공부(C++)

백준 2609 최소공배수 최대공약수

혀니리리 2022. 9. 2. 17:30
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
'알고리즘 공부(C++)' Related Articles more