BOJ 2609 최대공약수와 최소공배수

LONGNEW·2021년 1월 12일
0

BOJ

목록 보기
27/333
post-thumbnail

https://www.acmicpc.net/problem/2609
시간 1초, 메모리 128MB
input :

  • A B(1 <= A, B <= 10,000)

output :

  • 최대공약수, 최소 공배수 출력.

A의 약수들을 저장할. 1차원 리스트. B의 약수들 저장할. 1차원 리스트.

반복문의 경우. index라는 변수를 두고. index의 값이 계속 작아지는 형식.(약수들 1 이면 index 가 12, 약수가 2이면 index 가 6)
이렇게 가다가 어느 순간 나누기가 안 되고 index를 초과 하면 더 이상 약수가 없는것.

약수들은 다 구하면 정렬 해주자.

... 유클리드 호제법?

a와 b 의 최대공약수는 (a를 b로 나눈 나머지)와 b 의 최대공약수와 같다.
큰 수를 작은 수로 나누어 구한 나머지로 큰 수를 대체한다. 큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다. 나누어 떨어질 때(나머지가 0일 때), 나누는 수가 최대공약수이다

a, b = 315, 495
if(b>a) : 
    a,b = b,a

while(b!=0):
  a = a % b
  a, b = b, a

print(a)

정답 코드 :

import sys

A, B = map(int, sys.stdin.readline().split())

if B > A:
    a, b = B, A
else:
    a, b = A, B

while b != 0:
    a = a % b
    a, b = b, a

print(a)
print(A * B // a)


A 와 B가 마지막에 최소 공배수를 구해야 하기 때문에 최대 공약수를 구할 때는 다른 변수들이 필요하다.

0개의 댓글