[BOJ 2609] 최소공약수, 최대공배수 (유클리드호제법)

유클리드 호제법

- 2개의 자연수의 최대공약수를 구하는 알고리즘

 

호제법

- 두 수가 서로 상대방수를 나누어 결국 원하는 수를 얻는 알고리즘

 

배경 : 두 자연수 a,b

1. a를 b로 나눈 나머지는 r이라 하면(a>b)

2.a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

 

그러면 

24, 18이 있다면

24를 18로 나눈 나머지는 6

그렇다면 24와 18의 최대공약수는 18과 6의 최대공약수와 같다

 

18을 6으로 나눈 나머지는 0

그러면 24와 18의 최대공약수

18과 6의 최대공약수 

6과 0의 최대공약수 

즉, 6이다.

 

최소공배수는 

(a*b)/최대공약수 로 구할 수 있다.

 

 

코드로 작성해보자.

 

package math_problem

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func RunBoj2609(){
	scanner := bufio.NewScanner(os.Stdin);
	scanner.Scan()
	inputArr := strings.Split(scanner.Text(), " ");
	A,_ := strconv.Atoi(inputArr[0]);
	B,_ := strconv.Atoi(inputArr[1]);

	maximumCommitment := gcd(A,B); 
	minumumAirDrain := (A*B)/maximumCommitment;

	fmt.Println(maximumCommitment)
	fmt.Println(minumumAirDrain)
}

func gcd(a int, b int) int{
	if a<b {
		c := a
		a = b;
		b = c;
	}

	if b==0{
		return a;
	}

	result := a%b;
	return gcd(b,result);
}