[백준 - 14476] 최대공약수 하나 빼기 - Java

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

14476번: 최대공약수 하나 빼기

 

누적합 문제이다.

 

0번째부터 시작해 n번째까지의 누적 최대공약수를 기록해두는 배열과, n번째부터 0번째까지 누적 최대공약수를 기록해두는 배열을 사용한다.

 

 

첫 번째 수인 8을 뺐을 때 0번째까지의 최대공약수는 없고, 48부터 12까지의 최대 공약수는 12이다.

따라서 8을 뺐을 때 최대공약수는 8이다. 

 

 

두 번째 수인 12를 뺐을 때, 1번째까지의 최대공약수는 8, 48에서 24까지의 최대공약수는 12이다.

8과 12의 최대공약수는 4이므로, 12를 뺐을 때 최대공약수는 4이다.

 

이런식으로 끝까지 진행하면, 어떤 수를 뺐을 때 최대값을 얻을 수 있는지 알아낼 수 있다. 

 

public class Main {
    public static void main(String[] args) throws Exception{
        int[] data;
        int[] LR;
        int[] RL;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        LR = new int[N];
        RL = new int[N];
        data = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++){
            data[i] = Integer.parseInt(st.nextToken());
        }

        LR[0] = data[0];
        RL[N-1] = data[N-1];

        for(int i=1; i<N; i++){
            LR[i] = GCD(LR[i-1], data[i]);
        }

        for(int i=N-2; i>=0; i--){
            RL[i] = GCD(RL[i+1], data[i]);
        }


        int max = 0;
        int maxIndex = 0;
        for(int i=0; i<N; i++){
            int gcd = 0;
            if(i==0){
                gcd = RL[1];
            }
            else if(i==N-1){
                gcd = LR[N-2];
            }
            else {
                gcd = GCD(LR[i-1], RL[i+1]);
            }

            if(data[i]%gcd!=0 && gcd > max){
                max = gcd;
                maxIndex = i;
            }
        }

        if(max!=0) System.out.println(max+" "+data[maxIndex]);
        else System.out.println("-1");

    }

    static int GCD(int a, int b){
        while(b!=0){
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
}