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

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

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

---

 

 

풀이

먼저, 유클리드 호제법과 누적합의 개념을 이용하여 풀었다.

 

유클리드 호제법에 대해선 아래에 설명을 해놓았다.

https://khu98.tistory.com/229

[알고리즘] 최소공배수와 최대공약수 C++

 

 

먼저 gcd_left배열과 gcd_right 배열을 선언해주었다.

gcd_left[i] = 1번째 원소~i번째 원소까지 숫자들의 최대공약수를,

gcd_right[i] = i번째 원소~ N번째 원소까지 숫자들의 최대공약수를 저장해주었다.

 

그런뒤, 다음과 같은 방법을 사용했다.

k번째 숫자를 제거했을때의 최대공약수 = gcd ( gcd_left[k-1], gcd_right[k+1] )

k번째 숫자를 제거했을때, 좌측부분의 최대공약수와 우측부분의 최대공약수의 최대공약수를 구했을때, 원래보다 커지면 갱신을 해주었다.

이 동작을 첫번째 원소~마지막원소까지 실행해주어 갱신해준다.

 

시간복잡도

유클리드 호제법을 이용했으므로, gcd_left와 gcd_right를 셋팅하는데 O(NlogN)시간이 걸렸고,

k번째 숫자를 제거하는 알고리즘은 O(N)시간이 걸리므로, 총 시간복잡도는 O(NlogN)이 된다.

 

코드

#include <iostream>
#include<algorithm>
using namespace std;

int gcd_left[1000001], gcd_right[1000001],arr[1000001];
int n;

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a%b);
	}
}



int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		if (i == 1) {
			gcd_left[i] = arr[i];
		}
		if (i == n) {
			gcd_right[i] = arr[i];
		}
	}

	for (int i = 2; i <= n; i++) {
		gcd_left[i] = gcd(arr[i], gcd_left[i - 1]);
		gcd_right[n - i+1] = gcd(arr[n - i+1], gcd_right[n - i+2]);
	}
	int maxValue = gcd_left[n];
	int index = -1;
	for (int i = 1; i <= n; i++) {
		int g = gcd(gcd_left[i - 1], gcd_right[i + 1]);

		if (maxValue < g) {
			int now = arr[i];
			if (arr[i] % g != 0) {
				maxValue = g;
				index = i;
			}
		}
	}
	if (index == -1) {
		cout << "-1\n";
	}
	else {
		cout << maxValue << " " << arr[index];
	}
	return 0;
}