백준|14476번|최대공약수 하나 빼기

문제설명
정수들을 입력받고 그 중 하나를 제외한 수들로 만들 수 있는 최대공약수 중 가장 큰 값을 구하는 문제입니다. 단 어떤 수를 빼고 구한 최대공약수는 빠진 수의 약수가 되서는 안됩니다.

작동 순서
1. 정수의 개수를 입력받습니다.
2. 정수들을 입력받습니다.
3. 호제법을 이용하여 첫번째부터 수부터 마지막 수까지 하나씩 수열에 더해가며 최대공약수를 구합니다.
4. 3번과 반대의 순서로 마지막수부터 첫번째수까지 하나씩 수열에 더해가며 최대공약수를 구합니다.
5. N번을 뺀 최대공약수는 n-1까지의 최대공약수와 n+1까지의 최대공약수 간의 최대공약수이므로 그 둘의 최대 공약수를 구해줍니다.
6. 위에서 구한 최대공약수로 N번을 나누었을 때 나누어 떨어지지 않는 경우 현재 가지고있는 최대공약수와 비교하여 더 큰값을 저장합니다.
7. 연산이 모두 끝나면 가장 큰 최대공약수와 그 최대공약수를 만들기위해 제외해야하는 숫자를 출력합니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 백준_14476번_최대공약수하나빼기 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] num = new int[N];
        int[] gcdArrLR = new int[N];
        int[] gcdArrRL = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) num[i] = Integer.parseInt(st.nextToken());

        gcdArrLR[0] = num[0];
        for(int i=1;i<N-1;i++) gcdArrLR[i] = getGcd(num[i], gcdArrLR[i-1]);

        gcdArrRL[N-1] = num[N-1];
        for(int i=N-2;i>=0;i--) gcdArrRL[i] = getGcd(num[i], gcdArrRL[i+1]);

        int max = 0;
        int except = -1;

        for(int i=0;i<N;i++){
            int gcd;
            if(i==0) gcd = gcdArrRL[1];
            else if(i==N-1) gcd = gcdArrLR[N-2];
            else gcd = getGcd(gcdArrLR[i-1], gcdArrRL[i+1]);
            if(num[i]%gcd!=0) {
                if(max<gcd){
                    max = gcd;
                    except = i;
                }
            }
        }
        if(except!=-1) System.out.printf("%d %d", max, num[except]);
        else System.out.print("-1");
    }
    static int getGcd(int a, int b){
        if(b==0) return a;
        else return getGcd(b, a%b);
    }
}