[c++] 백준 14476 (최대공약수 하나빼기, 누적합, 최대공약수, 유클리드 호제법)

최대공약수를 구하는 함수는 수는 유클리드 호제법을 이용하여 정의할 수 있다.

gcd(36, 8) => gcd(8, 36%8)

....gcd(36,8) => gcd(8,4) => gcd(4,0) => 최대공약수는 4가 된다.

int gcd(int a, int b){
	while(b != 0){
    	int r = a % b;
        a = b;
        b = r;
    }
    return b;
}

이를 활용하여 누적합을 적용해 본다.

number	8	12	24	36	48
L to R	8	4	4	4	4
R to L	4	12	12	12	48

각 L to R과 R to L을 구한 이유는 k수를 제외하고 최대공약수를 구할때 O(n) 시간복잡도로 구하기 위해서이다.

즉, k=8 , 최대공약수 = RL[1]

k=12, 최대공약수 = gcd(LR[0], RL[2])

k=24, 최대공약수 = gcd(LR[1], RL[3])

:

그러면 이 수들중 가장 큰 수를 구하고 조건에 맞춰 출력만 해주면 된다.

#include<iostream>
#include<vector>

using namespace std;

vector<int> num;
vector<int> LR;
vector<int> RL;


int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main() {
	int N;
	cin >> N;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		num.push_back(tmp);
		LR.push_back(0);
		RL.push_back(0);
	}


	//LR구하기
	LR[0] = num[0];
	RL[N - 1] = num[N - 1];
	for (int i = 1; i < N; i++) {
		LR[i] = gcd(LR[i - 1], num[i]);
	}
	//RL구하기
	for (int i = N - 2; i >= 0; i--) {
		RL[i] = gcd(num[i], RL[i + 1]);
	}

	//k값에 따른 차이 확인하기
	int big = 0;
	int index;
	for (int i = 0; i < N; i++) {
		int tmp = 0;
		if (i == 0) {
			tmp = RL[i + 1];
		}
		else if (i == N - 1) tmp = LR[i - 1];
		else {
			tmp = gcd(LR[i - 1], RL[i + 1]);
		}
		if (tmp > big) {
			big = tmp;
			index = i;
		}
	}
	if (num[index] % big == 0) {
		cout << -1;
	}
	else {
		cout << big << ' ' << num[index];
	}
}

누적합은 아주 다양하게 사용된다고 한다. 좀 더 문제를 풀어보며 유형을 살펴봐야겠다.