[C] 백준 2609번 최대공약수와 최소공배수

1. 문제이해

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

2609번: 최대공약수와 최소공배수

 

두 개의 정수를 입력받아, 두 수의 최대공약수와 최소공배수를 출력하는 알고리즘을 만드는 것이 목표이다.

 

 

 

2. 문제풀이

 

최대공약수와 최소공배수를 출력하는 알고리즘을 구현하기 위해 여러가지 공식을 찾아보다,

다음과 같은 공식을 발견했다.

유클리드 호제법 (출처:나무위키)

 

유클리드 호제법이란, 위와 같은 방법으로 최대공약수를 구하는 방법이다.

즉, 두 정수 a, b에 대해, a를 b로 나눈 나머지인 r을 이용해,

최종적인 나머지가 0이 될때까지 위의 과정을 반복하는 것이다.

 

출처:나무위키

 

위와 같은 다른 예시를 보면, b를 a로 나눈 나머지가 r1이다.

(여기서는 위의 예제와는 다르게 a,b 순서가 바뀌어있다.)

여기서 구한 r1을 가지고, 다시 a를 r1으로 나누고 r2를 구한다.

위와 같은 과정을 n번 반복했을때, 나머지가 0이 나온다면, 두 수 a,b의 최대공약수가 rn이 나오게 된다.

 

그렇다면 최소공배수는 어떤식으로 구하면 될까?

최소공배수는 비교적 간단한 방식으로 구할 수 있었다.

입력받은 두 정수 a, b에 대해, a x b = 최대공약수 x 최소공배수 라는 공식이 있다.

따라서, 최소공배수 = a x b / 최대공약수 라는 식으로 구할 수 있다.

 

 

 

3. 소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

// 유클리드 호제법 이용 (최대공약수)
int Euclidean(a, b) {
	int r = a % b;
	if (r == 0)
		return b;
	else
		return Euclidean(b, r);
}


int main() {
	int gcd, lcd;	// 최대공약수, 최소공배수
	int a, b;	// 입력받을 두 개의 정수
	scanf("%d %d", &a, &b);

	gcd = Euclidean(a, b);

	// 최소공배수 = a*b/최대공약수
	lcd = (a * b) / gcd;

	printf("%d\n%d", gcd, lcd);
	return 0;
}

위와 같이 유클리드 호제법을 이용하여 최대공약수를 구하는 함수를 구현했다.

a와 b를 입력받아 두 수의 나머지를 구하고,

나머지가 0이 될때까지 재귀호출을 통해 이를 반복하도록 하는 형식이다.

최소공배수는 메인 함수에서 a x b = 최대공약수 x 최소공배수라는 공식을 사용해 구해주었다.

 

 

---

오늘은 어제의 다리놓기 알고리즘에 비해 비교적 간단하게 끝났다..

어제의 다리놓기 알고리즘도 처음 보았을때는 간단해 보였다가

막상 풀어보려니 힘들어서, 오늘것도 설마 그러려나.. 했는데,

유클리드 호제법을 이용하면 금방 구현할 수 있는 알고리즘이었다.

파이썬으로 구현하면 다리놓기 알고리즘도 금방 구현하던데,

조만간 파이썬으로 연습을 해봐야겠다.😤