[JAVA] 백준 알고리즘 1934번 문제풀이 (최소 공배수)

 

 

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

1934번: 최소공배수

 

 

● 최소공배수 문제 (1934번)

​

Q. 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

 

 

 

 

 

 

import java.util.Scanner;

//1934번
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int count = sc.nextInt();
		
		for(int i=0;i<count;i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int gcdValue = gcd(a, b);
			int lcmValue = a*b/gcdValue;
			System.out.println(lcmValue);
		}
		
	}

        //최대공약수 구하는 메소드
	public static int gcd(int a, int b) {
		if (b > a) {
			int temp = a;
			a = b;
			b = temp;
		}
		if (b == 0) {
			return a;
		} else {
			return gcd(b, a % b);
		}
	}

}

최소공배수를 구하기위해 최대공약수를 구해서 풀어주었습니다. (유클리드 호제법 사용)

↓ 소스풀이 ↓

입력을 받기위해 scanner클래스의 sc인스턴스를 생성해줍니다.

사용자가 몇개의 입력변수를 만들지를 알기위해 count변수를 만들어줍니다.

그리고 0부터 count까지 반복문을 돌리고 최소공배수를 구할 두 자연수 입력을 a,b를 각각 입력받습니다.

gcdValue변수는 최대공약수의 변수입니다. gcd()메소드를 아래 만들어서 파라미터로 a,b를 넘겨줍니다.

gcd메소드에서 매개변수로 받은 a와 b를 값 둘중에 무엇이 더 큰지 비교해주고, a가 큰값으로 만들기위해 자리를 변경해줍니다.

if문을 통해 b가 0이면 a를 리턴해주고, 그렇지않다면 다시 재귀함수호출을 사용해서 (b,a%b)를 넘겨줍니다.

유클리드 호제법과 재귀함수호출을 사용해서 최대공약수(gcdValue)를 구해주었습니다.

리턴된 최대공약수를 기존에 입력받은 a와b를 이용해서 a*b/gcdValue 공식을 사용해서 한번에 최소공배수를 구해봤습니다.

 

 

 

< 백준알고리즘 강의를 보고 참고하였습니다! >

 

 

---