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

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

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

 

 

정답풀이

 

1. 반복문을 이용한 방법

import java.util.Scanner;
 
public class Main {
 	public static void main(String[] args) {
 		Scanner in = new Scanner(System.in);
		
		int a = in.nextInt();
		int b = in.nextInt();
 
		int d = gcd(a, b);	// 최대공약수
 
		System.out.println(d);
		System.out.println(a * b / d); //최소공배수
 	}
 
	// 최대공약수 반복문 방식
	public static int gcd(int a, int b) {
 		while (b != 0) {
			int r = a % b; // 나머지를 구해준다.
 			// GCD(a, b) = GCD(b, r)이므로 변환한다.
			a = b;
			b = r;
		}
		return a;
	}
}

 

 

2. 유클리드 호제법을 이용한 방법

import java.util.Scanner;
 
public class Main {
 	public static void main(String[] args) {
 		Scanner in = new Scanner(System.in);
		
		int a = in.nextInt();
		int b = in.nextInt();
 
		int d = gcd(a, b);	// 최대공약수
 
		System.out.println(d);
		System.out.println(a * b / d); //최소공배수
 
	}
 
	// 최대공약수 재귀 방식
	public static int gcd(int a, int b) {
		if (b == 0) return a;
  		return gcd(b, a % b);
	}
}

 

 

 

 

후기

알고리즘 문제 중 자주 등장하는 최대공약수와 최소공배수에 도전했지만 못 풀었다. 

결국 정답을 참고하여 코드를 이해할 수 있었다.

이 과정에서 "유클리드 호제법"이라는 방법을 처음 알게 되었다.

수학 공부가 필요하다는 사실을 깨닫며,,, 더 많은 문제를 접하고 경험을 쌓아야겠다.

 

---

 

참고
https://st-lab.tistory.com/154

https://seunghyum.github.io/algorithm/Euclidean-algorithm/#

https://tech.lonpeach.com/2017/11/12/Euclidean-algorithm/