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

<백준 14476번 최대공약수 하나 빼기>

사용한 알고리즘: 세그먼트 트리


세그먼트 트리로 N개의 수의 gcd를 쌓아올렸습니다. 따라서 arr[1] 은 전체 수들의 공통 gcd 를 나타내게 됩니다.

이후 N개의 수들을 하나씩 0으로 바꿔가며 전체 gcd (arr[1]) 의 변화를 체크했습니다.
이 과정에서 전체 gcd가 증가하는 경우 그 값과, 바꿔준 노드의 원래 값을 저장했습니다.
이때 업데이트 방식은 해당 노드를 0으로 바꾸는 것으로 했으며, 어떤 수 A 와 0 의 gcd(A,0) = A 임을 이용했습니다.

제한시간에 거의 딱 맞춰서 돌아간 것 같습니다. 사실 더 쉽거나 빠른 풀이가 있을 것 같습니다....

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 1<<20;
	int N, ans, temp, aka, Changed;
	int arr[2*MAX+1];
	int GCD(int x, int y){
	if(y==0) return x;
	else return GCD(y, x%y);
	return 0;
	}
	void update(int idx, int New){
	arr[idx] = New;
	while(idx>1){
	idx/=2;
	arr[idx] = GCD(arr[idx*2],arr[idx*2+1]);
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i){
	int num;
	cin >> num;
	update(MAX+i,num);
	}
	aka = arr[1];
	Changed = aka;
	for (int i = 0; i < N; ++i){
	temp = arr[MAX+i];
	update(MAX+i,0);
	if(arr[1]>Changed){
	Changed = arr[1];
	ans = temp;
	}
	update(MAX+i,temp);
	}
	if(Changed!=aka) cout << Changed << ' ' << ans << '\n';
	else cout << -1 << '\n';
	return 0;
	}

view raw BOJ 14476.cpp hosted with ❤ by GitHub