[백준 JAVA] 1934번/13241번 풀이 - 최소공배수

첫 번째 문제 : 1934번 

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 두 자연수 a,b에 대하여, a의 배수이면서 b의 배수인 자연수를 
 * a와 b의 공배수라고 한다.
 * 
 * 이 공배수 중에서 가장 작은 공배수를 최소 공배수라고 한다. 
 * 두 자연수가 주어졌을 때, a와b의 최소공배수를 구하시오.
 * @author Back
 *
 */
public class _1934 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//테스트 케이스 개수
		int t = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		//t개의 줄에 걸쳐 a,b가 주어진다. 
		for ( int i = 0; i < t; i++ ) {
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			int result = gcd(a,b); // 6 10 -> 2
			System.out.println((a/result)*b);
			
		}
	}
	
	public static int gcd(int a, int b) {
		
		while(b!=0) {
			int r = a % b;
			a = b;
			b = r;	
		}
		
		return a;
	}
	

}

 

두 번째 문제 : 13241번 

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 최소공배수
 * - 한 줄에 두 정수 a, b가 공백으로 구분되어 주어진다.
 * - 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. java 는 long형을 선언한다.
 * - 출력 : a와 b의 최소 공배수를 한 줄에 출력하시오.
 * @author Back
 *
 */
public class _13241 {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		long a = Long.parseLong(st.nextToken());
		long b = Long.parseLong(st.nextToken());
		
		long result = gcd(a,b);
		
		System.out.println((a*b)/result);
		
	}
	
	private static long gcd(long a, long b) {
		
		while(b != 0 ) {
			long r = a % b;
			a = b;
			b = r;	
		}
		
		return a;
	}

}

 

풀이

유클리드 호제법을 이용해서 최대공약수를 구하고 , 최대공약수로 최소공배수를 구한다! 

유클리드 호제법 개념 바로가기 👉🏻 https://backshren20.tistory.com/639

[알고리즘] 유클리드 호제법 (GCD)