실력키우기 최대공약수, 최소공배수(JAVA)

1002 : 최대공약수, 최소공배수

제한시간: 1ms    메모리제한: 64MB
해결횟수: 1226회    시도횟수: 3876회   

n개의 정수를 입력받아서 최대공약수와 최소공배수를 구하는 프로그램을 작성하여 보자.

 

첫째 줄에 N (2≤N≤10) 을 입력받고 다음 줄에 N개의 정수를 공백으로 구분하여 입력받는다.
입력받는 정수는 2이상 10 000 이하이다.데이터의 크기가 주어진 범위를 벗어나는 입력은 없다.

입력받은 정수들의 최대공약수와 최소공배수를 공백으로 구분하여 출력한다.최소공배수는 20억 이하의 정수이다.

[Copy] 3 2 8 10

[Copy] 2 40

?

1. /**************************************************************
2.     Problem: 1002
3.     User: a132034
4.     Language: Java
5.     Result: Success
6.     Time:158 ms
7.     Memory:9308 kb
8. ****************************************************************/
9.  
10.  
11. import java.util.Arrays;
12. import java.util.Scanner;
13.  
14. public class Main{
15.     public static void main(String[] args) {
16.         Scanner sc = new Scanner(System.in);
17.         int N = sc.nextInt();
18.         int[] arr = new int[N];
19.          
20.         int GCD = 0, LCM = 0 ;
21.         for(int i = 0 ; i < N; ++i)
22.             arr[i] = sc.nextInt();
23.         Arrays.sort(arr);
24.         GCD = arr[N-1];
25.         LCM = arr[N-1];
26.  
27.         for(int i = N-2 ; i >= 0; --i)
28.         {
29.             int x, y;
30.             if(GCD > arr[i]){
31.                 x = GCD; y = arr[i];
32.             }
33.             else{
34.                 y = GCD; x = arr[i];
35.             }
36.             GCD = getGcd(x, y);
37.              
38.             if(LCM > arr[i]){
39.                 x = LCM; y = arr[i];
40.             }
41.             else{
42.                 y = LCM; x = arr[i];
43.             }
44.  
45.             LCM = (x * y) /  getGcd(x, y);
46.  
47.         }
48.         System.out.println(GCD + " " + LCM);        
49.     }
50.      
51.     public static int getGcd(int x, int y)
52.     {
53.         if(x % y == 0) return y;
54.         return getGcd(y, x%y);
55.     }
56. }

기존의 최대공약수, 최소공배수를 활용하지만 이번에는 두 수간의 문제가 아닌 여러 수의 최대공약수와 최소공배수를 구하는 문제였다. 

사실 도움말을 읽어보면.. 어렵지 않다.

두 개의 수 A와 B의 최대공약수를 D라 하면, 세 개의 수 A, B, C의 최대공약수는 D와 C의 최대공약수와 같다. 이런 규칙을 이용하면 두 수의 최대공약수를 
구하는 함수 한 개만으로도 여러 수의 최대공약수를 구할 수 있다. 
최소공배수 역시 두 수의 최소공배수를 구해 나가는 방법으로 구할 수 있다. 
a배열에 N개의 수가 저장되어 있다고 가정한다면 다음과 같이 구현할 수 있다.

코드
01    gcd = lcm = a[0];
02    for (i=1; i < N; i++) {
03        gcd = gcd_get(gcd, a[i]);
04        lcm = lcm * a[i] / gcd_get(lcm, a[i]);
05    }

코드분석
첫 번째 수를 최대공약수(gcd)로 정하고 두 번째 수부터 이전까지의 최대공약수(gcd)와 현재 배열의 값(a[i])의 최대공약수를 구하여 다시 gcd에 저장한다. 
이러한 작업을 마지막까지 반복하면 모든 수의 최대공약수가 구해진다.
최소공배수도 같은 방법으로 구할 수 있다.

크게 어려울 것이 없다. 

맨 위의 규칙을 이용한다면 ( A B의 최대공약수가 D일 때 -> A B C의 최대공약수는 D C의 최대공약수와 같다 )

두 수간의 최대공약수, 최소공배수를 구한 후 -> 구해진 최대공약수, 최소공배수와 다음 수의 최대공약수, 최소공배수를 구하면 된다. 

이때, 코드에서 주의했던 점은.. 최대공약수(gcd)를 구하는 함수에서 x가 y보다 커야 할 것. 

이때문에 for loop를 사용했고, 정렬도 한 후에 구하기 시작했는데..  아래에서 조건으로 큰 수를 x에 넣어줌으로써.. 사실상 loop와 정렬은 필요가 없다. 

아니라면 아에 함수 내에 x, y의 크기를 비교하여준다면 더 편했을 것 같기도 하다.