[Java] 백준 9417번 : 최대GCD

문제

https://www.acmicpc.net/problem/9417

 

접근 방법

1. 정수 M이 주어졌을때 모든 두 쌍 중에서 가장 큰 최대공약수를 찾는 문제이다.
2. M이 최대 99이므로 2쌍을 찾을때 완탐을 해도 N*10000의 경우의 수보다 작다.
3. 유클리드 호제 방법으로 문제를 쉽게 풀 수 있었다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int T;
    private static ArrayList<Integer> list;
    private static int max;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());

        for(int tc = 0 ; tc < T ; tc++){
            String[] arr = br.readLine().split(" ");

            list = new ArrayList<Integer>();

            for(int i = 0 ; i < arr.length ; i++){
                list.add(Integer.parseInt(arr[i]));
            }

            process();
        }
    }
    
    //유클리드 호제법
    public static void gcd(int a, int b){
        while (a%b != 0){
            int temp = a%b;
            a = b;
            b = temp;
        }

        if(max<b){
            max = b;
        }
    }

    //실행
    public static void process() {
        max = Integer.MIN_VALUE;

        for(int i = 0 ; i < list.size()-1; i++){
            for(int j = i+1 ; j < list.size(); j++){
                gcd(list.get(i),list.get(j));
            }
        }

        sb.append(max).append("\n");
    }


    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb.toString());
    }
}