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

📎 문제링크

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

📄 문제설명

정수 A가 B로 나누어 떨어지면, B는 A의 약수이고 A는 B의 배수이다.

최대공약수란 정수의 공통된 약수 중 가장 큰 수를 말한다. 예를 들어, 12와 8의 공통된 약수 1, 2, 4 중에서 가장 큰 것은 4이기 때문에 12와 8의 최대공약수는 4이다.

N개의 정수 중에서 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지는 것을 찾는 프로그램을 작성하시오. 이때, 최대공약수는 K의 약수가 되면 안 된다.

예를 들어, 정수 8, 12, 24, 36, 48에서 8을 빼면 나머지 12, 24, 36, 48의 최대공약수는 12가 되고, 12는 빠진 수 8의 약수가 아니기 때문에 정답이 될 수 있다. 이때, 다른 수를 빼도 최대공약수가 8보다 커질 수 없다.

하지만, 8, 12, 20, 32, 36의 경우에는 그 무엇을 빼더라도 나머지 수의 최대공약수가 K의 약수가 되기 때문에, 정답을 구할 수 없다.

N개의 수가 주어졌을 때, 정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수를 구하는 프로그램을 작성하시오.

입력

GCD(a,b)-> a=b,b=a%b->GCD(a,b)-> b=0이 될때 a의 값이 GCD가 된다라는 유클리드 호제법을 이용해서 푸는 문제로 이후에는 누적합을 통해 왼쪽->오른쪽 GCD, 오른쪽->왼쪽 GCD 를 배열에 집어놓고 빼고 싶은 인덱스의 값만 제외하여 GCD를 구할수 있다

📝 문제풀이

💡 Code

코드

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

public class Main {

     static int N;
     static int M[];  // 배열

     static int LtoR[];
     static int RtoL[];
     
    public static void main(String[]args)throws IOException {
       
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        M=new int[N];
        StringTokenizer st=new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {          //배열 저장

            M[i]=Integer.parseInt(st.nextToken());

        }
        LtoR=new int[N];
        RtoL=new int[N];
        // 왼쪽 부터 gcd누적합 구하기
        LtoR[0]=M[0]; // 첫 자리는 최대 공약수 자기자신
        for (int i = 1; i <N; i++) {
            LtoR[i]=gcd(LtoR[i-1],M[i]);
        }
        // 오른쪽 끝부터 gcd누적합 구하기
        RtoL[N-1]=M[N-1];
        for (int i =N-2; i>=0 ;i--) {
            RtoL[i]=gcd(RtoL[i+1],M[i]);
        }

        int max=0;
        int K=0;
        int gcd=0;
        //i 값기준 LtoR(0 ~ i-1) RtoL(i+1 ~N-1)
        for (int i = 0; i < N-1; i++) {

            if(i==0){
                gcd=RtoL[1];
            }
            else if(i==N-1){
                gcd=LtoR[N-2];
            }
            else {
                gcd = gcd(LtoR[i - 1], RtoL[i + 1]);
            }
            // K % gcd==0
            if(max<gcd && M[i]%gcd!=0){
                max=gcd;
                K=M[i]; //뺀수
            }
        }
        if (max==0){    // 최대공약수 x
            System.out.println(-1);
        }
        System.out.println(max+" "+K);

    }
    static int gcd(int a,int b){   
      int r;
        while(b!=0){

            r = a%b;
            a =b;
            b = r;
        }
        return  a;
    }
}

👍 Comment