[백준] 14476번 최대공약수 하나 빼기 (JAVA)

문제

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

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

 

설명

N개의 정수 중에서 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지게 해야 한다.

모든 경우의 수를 하나하나 따지면 수행시간이 O(\(N^{2}\)) 이지만 누적합을 사용하면 O(N) 으로 해결할 수 있다.

LtoR 배열에는 배열 좌측에서부터 하나씩 누적해서 구한 최대공약수를 저장한다.

RtoL 배열에는 배열 우측에서부터 하나씩 누적해서 구한 최대공약수를 저장한다.

최대공약수를 구할 때에는 유클리드 호제법을 사용한다.

LtoR = new int[N];
LtoR[0] = nums[0];
for (int i = 1; i < N; i++) {
    LtoR[i] = gcd(LtoR[i - 1], nums[i]);
}

RtoL = new int[N];
RtoL[N - 1] = nums[N - 1];
for (int i = N - 2; i >= 0; i--) {
    RtoL[i] = gcd(RtoL[i + 1], nums[i]);
}


// 최대공약수 구하는 함수
int gcd(int a, int b) {
    if (a % b == 0) {
        return b;
    }
    
    return gcd(b, a % b);
}

result 배열에는 각 인덱스에 해당하는 수를 제외한 나머지 N-1개의 최대공약수를 저장한다.

LtoR 배열과 RtoL 배열을 이용하여 result 배열을 채울 수 있다.

result 배열에서 가장 큰 수와 그 최대공약수를 구할 때 제외한 수를 구한다.

int[] result = new int[N];
result[0] = RtoL[1];
result[N - 1] = LtoR[N - 2];
for (int i = 1; i < N - 1; i++) {
    result[i] = gcd(LtoR[i - 1], RtoL[i + 1]);
}

int answer = 0;
int except = 0;
for (int i = 0; i < N; i++) {
    if (nums[i] % result[i] != 0 && answer < result[i]) {
        answer = result[i];
        except = nums[i];
    }
}

 

전체 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int[] nums;
    static int[] LtoR, RtoL;

    // 최대공약수 구하는 함수
    static int gcd(int a, int b) {
        if (a % b == 0) {
            return b;
        }

        return gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

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

        LtoR = new int[N];
        LtoR[0] = nums[0];
        for (int i = 1; i < N; i++) {
            LtoR[i] = gcd(LtoR[i - 1], nums[i]);
        }

        RtoL = new int[N];
        RtoL[N - 1] = nums[N - 1];
        for (int i = N - 2; i >= 0; i--) {
            RtoL[i] = gcd(RtoL[i + 1], nums[i]);
        }

        int[] result = new int[N];
        result[0] = RtoL[1];
        result[N - 1] = LtoR[N - 2];
        for (int i = 1; i < N - 1; i++) {
            result[i] = gcd(LtoR[i - 1], RtoL[i + 1]);
        }

        int answer = 0;
        int except = 0;
        for (int i = 0; i < N; i++) {
            if (nums[i] % result[i] != 0 && answer < result[i]) {
                answer = result[i];
                except = nums[i];
            }
        }

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