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

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

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

최초풀이

#include <iostream>
#include <vector>

int arr[44722];

using namespace std;
// 1-2,000,000,000->44,722
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, k;
	vector<int>v, ans;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> k;
		v.push_back(k);
	}
	for (int i = 0; i < N; i++) {
		for (int j = 2; j < 44722; j++) {
			if (v[i] < j) break;
			if (v[i] % j == 0)
				arr[j]++;
		}
	}

	for (int i = 0; i < 44722; i++) {
		if (arr[i] == N - 1)
			ans.push_back(i);
	}

	if (ans.size() == 0) cout << -1;
	else {
		for (int i = 0; i < N; i++) {
			if (v[i] % ans[ans.size() - 1] != 0) {
				cout << ans[ans.size() - 1] << " " << v[i];
				break;
			}
		}
	}

	return 0;
}

>> 시간초과 에러발생

 

해결

처음 수들에 대한 왼쪽, 오른쪽 누적 최대공약수(GCD)를 구해줍니다.

그리고 i인덱스를 기준으로 왼쪽 최대 공약수 i-1, 오른쪽 최대 공약수 i+1인덱스의 최대공약수를 구합니다.

여기서 구해진 최대 공약수가 i인덱스의 숫자를 제외했을 때 나머지 수들의 최대공약수이므로 이 수의 최대 값을 구합니다.

#include <iostream>
using namespace std;
int L_gcd[1000001], R_gcd[1000001], arr[1000001];

int gcd(int a, int b) {// 최대공약수 구하기(재귀, 유클리드 호제법)
	if (b == 0) return a;
	else return gcd(b, a % b);
}

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) 
		cin >> arr[i];
	for (int i = 1; i <= n; i++)// 왼쪽에서부터 누적해서 공약수를 구함 
		L_gcd[i] = gcd(arr[i], L_gcd[i - 1]);
	for (int i = n; i >= 1; i--) // 오른쪽에서부터 누적해서 공약수를 구함
		R_gcd[i] = gcd(arr[i], R_gcd[i + 1]);

	int Num = -1;// 뺄 숫자
	int Max = 0;// 가장 큰 최대공약수
	for (int i = 1; i <= n; i++) {
		int gcdResult = gcd(L_gcd[i - 1], R_gcd[i + 1]);// i인덱스의 값을 빼고 나머지 수들 간의 최대 공약수를 구함
		if (gcdResult > Max && (arr[i] % gcdResult)) {// 최대 공약수를 가장 큰 값으로 갱신/선택된 최대 공약수가 뺀 i인덱스 수의 약수이면 안되는 조건 추가
			Max = gcdResult;
			Num = arr[i];
		}
	}

	if (Num == -1) cout << Num;
	else cout << Max << " " << Num;

	return 0;
}