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

백준 14476 최대공약수 하나 빼기 문제
백준 14476 최대공약수 하나 빼기 소스코드

📄 문제 설명

Problem

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

Input

첫째 줄 : 정수의 개수 N (4 ≤ N ≤ 1,000,000)
다음 N개의 줄 : N개의 20억을 넘지 않는 자연수

Output

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

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

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

Example Input 1

5
8 12 24 36 48

Example Output 1

12 8

Example Input 2

5
8 12 20 32 36

Example Output 2

-1

📝 문제 해설

이 문제는 N개의 정수중 하나를 제외했을 때 만들수 있는 가장 큰 최대공약수를 구하는 문제이다.

왼쪽부터 차례로 최대공약수를 누적한 배열(LtoR)과
오른쪽부터 차례로 최대공약수를 누적한 배열(RtoL)을 구하고
두 배열을 이용해 최대공약수의 최댓값을 찾아가면 된다.

▶ 유클리드 호제법 ( 최대공약수 구하는 알고리즘)

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다.
2개의 자연수 a, b 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a > b)
a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용.

152와 68의 최대공약수(Greatest Common Divisor) 구하기

  a     b    r (= a % b)
152    68   16
    ↙    ↙
 68    16    4
    ↙    ↙
 16     4    0
    ↙    ↙
  4     0    0

b값이 0이 되면 그 때의 a값이 최대공약수가 된다.
→ GCD(152, 68) = 4

int gcd(int a, int b){
    return b ? gcd(b, a%b) : a; //(b가 0이 아니면 : b가 0이면)
}

문제로 돌아와서,

예를 들어) n이 5일 때, 정수 배열(num)이 주어지면 LtoR, RtoL배열은 아래와 같다.

LtoR 배열은 [i]번째 자리에 num[0] ~ num[i]까지의 최대공약수가 들어가고,
RtoL 배열은 [i]번째 자리에 num[i] ~ num[n-1]까지의 최대공약수가 들어간다.

ⓐ num[0]을 제외했을 때 RtoL[0+1] 값이 최대 공약수이고,

ⓑ num[n-1]을 제외했을 때 LtoR[(n-1)-1]의 값이 최대공약수가 된다.

ⓒ [0]과 [n-1]사이의 i번째인 num[i]를 제외했을 때의 최대공약수는
   LtoR[i-1]과 RtoL[i+1]의 최대공약수가 된다.
   ex) num[2]인 24를 제외했을 때 최대공약수는 LtoR[2-1]과 RtoL[2+1] (4와 12)의
       최대공약수인 4가 된다.

위의 사항을 유의하며 문제를 풀면 된다.

</> Source Code

#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

int main() {
	int n;
	scanf("%d", &n);

	vector<int> num;
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		num.push_back(x);
	}

	vector<int> LtoR(n);
	vector<int> RtoL(n);

	LtoR[0] = num[0];
	RtoL[n - 1] = num.back();

	//LtoR
	for (int i = 1; i <= n - 1; i++) {
		int val = LtoR[i - 1];
		LtoR[i] = gcd(max(val, num[i]), min(val, num[i]));
	}

	// RtoL
	for (int i = n - 2; i >= 0; i--) {
		int val = RtoL[i + 1];
		RtoL[i] = gcd(max(val, num[i]), min(val, num[i]));
	}

	int result = -1;
	int except = -1;

	for (int i = 0; i < n; i++) {
		if (i == 0) {
			result = max(result, RtoL[1]);
			except = num[i];
		}
		else if (i == n - 1) {
			if (result < LtoR[n-2]) {
				result = LtoR[n-2];
				except = num[i];
			}
		}
		else {
			if (result < gcd(LtoR[i - 1], RtoL[i + 1])) {
				result = gcd(LtoR[i - 1], RtoL[i + 1]);
				except = num[i];
			}
		}
	}

	if (except % result == 0) {
		printf("-1");
	}
	else {
		printf("%d %d", result, except);
	}

	return 0;
}