본문 바로가기

Dot Algo∙ DS/PS

[BOJ] 백준 2824번 최대공약수 (Java)

    #2824 최대공약수

    난이도 : 골드 5

    유형 : GCD

     

    2824번: 최대공약수

    첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M(1 ≤ M ≤ 1000)이

    www.acmicpc.net

    ▸ 문제

    상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.

    상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.

    이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

     입력

    첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.

    셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를 곱하면 B가 된다.

     출력

    두 수의 최대공약수를 출력한다. 만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

     

    문제 풀이  

    두 수의 최대공약수를 구해주면 된다. 그냥 A와 B를 바로 구해서 유클리드 호제법으로 바로 구해도 되지만 그러면 기존 자바 자료형 변수로는 구할 수 없다. 각 수의 범위가 최대 10억이다보니 오버플로가 발생한기 때문이다. 그래서 BigInteger이라는 라이브러리를 사용해줘야 한다.

     

    그런데 그냥 GCD 구하는 연습 겸 풀이를 하려면 주어지는 A와 B의 공약수를 일일이 모두 구한 다음 공통되는 최대공약수를 곱해주면서 오버플로가 발생하지 않게 1_000_000_000가 넘어가는 부분에서 값을 나눠줘서 구해주면 된다.

     

     

    풀이 코드 

    import java.io.*;
    import java.util.*;
    
    public class Main {
    
    	public static void main(String[] args) throws IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		StringTokenizer st;
    		int n = Integer.parseInt(br.readLine());
    		
    		Map<Integer, Integer> aMap, bMap;
    		
    		aMap = new HashMap<>();
    		long a = 1L, b = 1L;
    		st = new StringTokenizer(br.readLine());
    		for(int i=0; i<n; i++) {
    			int num = Integer.parseInt(st.nextToken());
    			getCommonFactor(num, aMap);
    		}
    		
    		bMap = new HashMap<>();
    		int m = Integer.parseInt(br.readLine());
    		st = new StringTokenizer(br.readLine());
    		for(int i=0; i<m; i++) {
    			int num = Integer.parseInt(st.nextToken());
    			getCommonFactor(num, bMap);
    		}
    		
    		boolean flag = false;
    		long gcd = 1L;
    		for(int key : aMap.keySet()) {
    			if(bMap.containsKey(key)) {
    				int min = Math.min(aMap.get(key), bMap.get(key));
    				for(int i=0; i<min; i++) {
    					gcd *= key;
    					if(gcd>=1_000_000_000) {
    						gcd %= 1_000_000_000;
    						flag = true;
    					}
    				}
    			}
    		}
    		if(flag) {
    			System.out.printf("%09d", gcd);
    			return;
    		}
    		System.out.println(gcd);
    	}
        
    	static void getCommonFactor(int num, Map<Integer, Integer> map) {
    		for(int i=2; i*i<=num; i++) {
    			while(num%i ==0) {
    				map.put(i, map.getOrDefault(i, 0)+1);
    				num /=i;
    			}
    		}
    		if(num != 1) map.put(num, map.getOrDefault(num, 0)+1);
    	}
    }