문제 풀이 전 이론 - 1
- 최대공약수는 줄여서 GCD라고 한다.
- 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.
- 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법이 있다.
- min(A,B)인 이유는 어차피 두 수의 공통된 약수 중 가장 큰 정수는 min(A,B)보다 크지 않기 때문이다.
- 위의 이론은 O(N)이고, 입력이 10,000이하이기 때문에 시간 제한 1초 내에는 충분히 실행가능하다.
- 하지만 이보다 더 빠른 방법으로 문제를 해결하기 위해 유클리드 호제법]을 사용해본다.
int g =1;
for(int i = 2; i <= min(a,b); i++){
if(a%i == 0 && b%i == 0){
g = i;
}
}
문제 풀이
- a를 b로 나눈 나머지를 r이라고 했을 때
- GCD(a,b) = GCD(b,r)과 같다.
- r이 0이되면 그 때 b가 최대공약수이다.
- 코드로 구할 때는 r이 0이 될 때까지 재귀함수를 호출하여 해결할 수 있다.
- 최소공배수는 LCM라고 한다.
- a를 최대공약수로 나누었을 때의 몫, b를 최대공약수로 나누었을 때의 몫을 구한 후
- 최대공약수에 곱해주면 된다.
- G x (a/G) x (b/G) = 최소공배수
소스 코드
public class Main {
public static void main(String[] args) {
int a,b,r,min,maxres = 0,minres = 0;
Scanner scan = new Scanner(System.in);
a = scan.nextInt();
b = scan.nextInt();
maxres = GCD(a,b);
minres = LCM(a,b,maxres);
System.out.println(maxres);
System.out.println(minres);
}
public static int GCD(int a,int b) {
if(b == 0) {
return a;
}else {
return GCD(b,a%b);
}
}
public static int LCM(int a,int b, int gcd) {
return gcd * a/gcd * b/gcd;
}
}
출력
문제로부터 얻어간 것
이 문제는 유클리드 호제법을 사용하지 않아도 충분히 풀 수 있었지만, 입력 값을 더 크게 받음으로 인해서 실행시간이 초과되는 경우에 사용할 수도 있어 매우 편리하다고 생각한다. 코드도, 이론도 어렵지 않기 때문에 더욱 유용하다.
'기타등등 > 알고리즘 기록' 카테고리의 다른 글
[JAVA] 백준 1929 - 소수 찾기2 (에라토스테네스의 체) (0) | 2021.02.24 |
---|---|
[JAVA] 백준 1978 - 소수 찾기 (0) | 2021.02.24 |
[JAVA]백준 17425 - 약수의 합 (0) | 2021.02.20 |
[JAVA]백준 17427 - 약수의 합2 (0) | 2021.02.18 |
[JAVA]백준 1037번 - 약수 (0) | 2021.02.18 |