‡ CODING TEST STUDY ‡/º 백준
[백준 | Java Bronze VI] (#2609) 최대공약수와 최소공배수
Trudy | 송연
2024. 6. 22. 21:23
문제
https://www.acmicpc.net/problem/2609
첫번째 코드 - 성공
첫번째로 가장 직관적인 최대공약수/최소공배수를 구하도록 풀었던 코드이다. 다른 효율적인 방법이 있었던 것 같지만 풀 때 기억이 나지 않았다
package week8.baek;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class B2609 {
//최대 공약수
public static int max(int a, int b){
System.out.println(a + " " + b);
for(int i=b; i>0; i--){
if(a % i == 0 && b % i == 0) return i;
}
return -1;
}
//최소 공배수
public static int min(int a, int b){
for(int i=b; i <= a*b; i++){
if(i % a == 0 && i % b == 0) return i;
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int n = Integer.parseInt(input.split(" ")[0]);
int m = Integer.parseInt(input.split(" ")[1]);
int[] a = new int[] {n, m};
Arrays.sort(a);
System.out.println(max(a[0],a[1]) + "\n" + min(a[0],a[1]));
}
}
개선 1 - (A와 B의 최소 공배수) = (A * B) / (A와 B의 최대 공약수)
package week8.baek;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class B2609 {
//최대 공약수
public static int max(int a, int b){
System.out.println(a + " " + b);
for(int i=b; i>0; i--){
if(a % i == 0 && b % i == 0) return i;
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int n = Integer.parseInt(input.split(" ")[0]);
int m = Integer.parseInt(input.split(" ")[1]);
int[] a = new int[] {n, m};
Arrays.sort(a);
int max = max(a[0], a[1]);
System.out.println(max(a[0],a[1]) + "\n" + n * m / max);
}
}
개선 2 - 유클리드 호제법
static int gdc(int a, int b) {
if(a<b) // 유클리드 호제법 조건
{
int temp = a;
a = b;
b = temp;
}
while(b!=0) { // 유클리드 호제법
int r=a%b;
a=b;
b=r;
}
return a;
}
출처
[Java]최대 공약수, 최소 공배수 구하기(feat.유클리드 호제법)
안녕하세요 코북입니다. 오늘은 최대 공약수와 최소 공배수를 구하는 문제를 풀어봤습니다. 풀이가 다양하여 제가 푼 방식을 공유해보려고 합니다. 첫 번째 방식은 문제에 나와있는 것처럼 최
cobook.tistory.com