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

#14476 최대공약수 하나 빼기

난이도 : 골드 2

유형 : 정수론 / 유클리드 호재법

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

▸ 입력

첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다.

▸ 출력

첫째 줄에 정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수를 출력하고, 공백을 출력한 다음 뺀 수를 출력한다.

뺀 수를 K라고 했을 때, 나머지 수의 최대공약수가 K의 약수가 되면 안 된다.

만약 정답이 없는 경우에는 -1을 출력한다.

 

문제 풀이  

i번째 수를 뺀 최대 공약수를 구하기 위해서 다음과 같이 lgcd와 rgcd를 구해줘야 한다. lgcd[i]는 1~  i번까지의 최대공약수를 구해준 것이고 rgcd[i]는 i+1 ~ n번까지의 최대공약수를 구해준 것이다. 그래서 gcd(lgcd[i-1], rgcd[i+1]의 값을 구하면 수열에서 arr[i]를 뺀 최대공약수를 구할 수 있다.

 

arr	8	12	24	36	48
lgcd	8	4	4	4	4
rgcd	4	12	12	12	48

 

i = 1, arr[i] = 8을 뺀 수열의 최대공약수는 lgcd[0] = 0, rgcd[2] = 12 이므로 (0은 무시) 12임을 알 수 있다. 

• 그렇게 구한 최대공약수(12)는 arr[i]과 나누어떨어지면 안된다. 나누어떨어지면 arr[i]이 있을 때도 포함되는 최대공약수이기 때문이다. 예로 i=2, arr[i] =12을 뺐을 때 lgcd[1] = 8, rgcd[3] = 12이고 최대공약수는 4가 나온다. 

 

풀이 코드 

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[n+2];
		for(int i=1; i<=n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] lgcd = new int[n+2];
		for(int i=1; i<=n; i++) {
			lgcd[i] = gcd(arr[i], lgcd[i-1]);
		}
		
		int[] rgcd = new int[n+2];
		for(int i=n; i>0; i--) {
			rgcd[i] = gcd(arr[i], rgcd[i+1]);
		}
		
		int ans = -1;
		int max = -1;
		for(int i=1; i<=n; i++) {
			int res = gcd(lgcd[i-1], rgcd[i+1]);
			if(res > max) {
				if(arr[i]%res !=0) {
					max = res;
					ans = arr[i];
				}
			}
		}
		
		if(ans == -1) {
			System.out.println(-1);
		}else {
			System.out.println(max+" "+ans);
		}
	}
	
	static int gcd(int a, int b) {
		if(b == 0) {
			return a;
		}else {
			return gcd(b, a%b);
		}
	}
}