BOJ(2609) - Kotlin

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

나의 접근방법

최대공약수를 위한 알고리즘 중에 '유클리드 호제법'이라는 알고리즘이 있다. 이 알고리즘을 구현해 문제를 풀려고 했다. 최대공약수를 구하기만 하면 최소공배수는 각 수를 최대공약수로 나눈 몫 X 최대공약수 이기 때문에 이 알고리즘을 구현하는게 가장 중요한 문제였다. '유클리드 호제법'이 무엇인지 궁금하다면 구글링을 해보시기 바란다.

여기서 간단하게 설명하자면 두 수를 나눈 나머지가 0이 될 때까지 계속 나눴을 때 0으로 만드는 작은 수가 최대공약수가 된다는 알고리즘이다. 솔직히 중, 고등학교 때 이런 알고리즘이 있었는지 전혀 몰랐던 것 같다. 암튼 이 알고리즘을 구현하기 위해서 나는 큰 수와 작은 수를 픽스해주려고 두 수의 크기에 맞춰서 계산을 하도록 코드를 구현했다.

코드

/* 최대공약수와 최소공배수 */

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val num1 = nextInt()
    val num2 = nextInt()
    val gcd: Int

	// 지속적으로 계산하기 위해 쓰일 변수
	var n1 = num1
	var n2 = num2
    
	// 지속적인 나눗셈을 위한 반복문
	while (true) {
		var tmp: Int

		// 맨 처음 입력받는 두 수 중 어느 것이 큰 수인지를 알 수 없어 만든 조건문
		if (n1 > n2) {
        	// 첫번 째 이후로는 계속해서 이 조건으로 분기할 것이다.
        	// 왜냐하면 밑에서 n1을 큰 수로 설정해주기 때문
			tmp = n1 % n2
			n1 = n2
		} else {
			tmp = n2 % n1
            }
		n2 = tmp

		
		if (n2 == 0) {		// 나머지가 0이 됐을 때 최대공약수 출력하고 반복문 종료
			println(n1)		// 최대공약수 출력
			gcd = n1
			break
            }
        }
	println(gcd*(num1/gcd)*(num2/gcd))	// 최소공배수 출력
}