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

문제

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

 

접근 방법

1. left 배열은 i번째 자리에 arr[1] ~ arr[i] 까지 최대 공약수를 넣어줍니다.

2. right 배열은 i 번째 자리에 arr[i+1] ~ arr[i] 까지 최대 공약수를 넣어줍니다.

3. 따라서 어떤 수 i를 뺀 나머지에서 최대공약수를 구한다면 left[i-1]과 right[i+1]의 최대공약수를 구해주면 됩니다.

4. 그렇게 구한 최대공약수로 i를 나누려 할때 나누어지면 안되고, 제일 큰 최대공약수를 저장해야 됩니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
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 N;
    private static int[] arr,left,right;


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

        N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        left = new int[N+1];
        right = new int[N+1];

        st = new StringTokenizer(br.readLine());
        for(int i = 1 ; i <= N ; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
    }
    
    //유클리드 호제법
    public static int gcd(int a, int b){
        int temp = 0;

        while ( a%b !=0 ){
            temp = a%b;
            a = b;
            b = temp;
        }
        return b;
    }

    //실행
    public static void process() {
        left[1] = arr[1];
        right[N] = arr[N];

        for(int i = 2 ; i <= N ; i++){
            left[i] = gcd(left[i-1],arr[i]);
        }

        for(int i = N-1; i >=1 ; i--){
            right[i] = gcd(right[i+1],arr[i]);
        }

        int answer = 0;
        int value = 0;
        for(int i = 1 ; i < N ; i++){
            int current = gcd(left[i-1],right[i+1]);

            if(arr[i]%current != 0 && value < current){
                answer = arr[i];
                value = current;
            }
        }

        if(answer == 0 && value == 0){
            System.out.println(-1);
        }else{
            System.out.println(value+" "+answer);
        }
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}