[알고리즘] 백준 9613번: GCD 합 (C++), 유클리드 호제법, 최대공약수를 빠르게 구하는 방법

이 문제는 크게 고민할 필요 없이 백트래킹으로 쌍 구하고, 최대공약수를 구해 더해나가면 되는 문제였다.

하지만 이를 구현했을 때, 시간 초과가 발생한다.

---

코드 (시간 초과)

백트래킹에서 발생하는 것인지, 최대공약수를 구하는 함수에서 발생하는 것인지 알 수 없었다.

하지만, 1,000,000을 넘지 않는 수라면 그에 근접하는 엄청 큰 수들이 100개까지 있다고 생각해보면 몇 쌍들이 생길지 모를뿐더러 거기다가 곱하기 1,000,000을 해준다면 엄청 큰 값이 나와서 시간 초과를 유발하는 것을 알 수 있었다.

>> 최대공약수를 구하는 함수가 문제다.

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

bool visited[101] = { 0, };
vector<int> two; // 두 수 고른 거 담을 배열
int sum; // gcd 총합 구할 변수

void gcd(vector<int>& two) { // 최대공약수
	int n = two[0], m = two[1];

	if (n > m) {
		int temp = n;
		n = m;
		m = temp;
	}

	int value = 0;
	for (int i = 1; i <= n; i++) {
		if (n % i == 0 && m % i == 0) {
			value = i;
		}
	}


	sum += value;
	return;
}

void sol(vector<int>& arr, int n, int idx) { // 백트래킹
	if (n == 2) {
		gcd(two);
		return;
	}

	for (int i = idx; i < arr.size(); i++) {
		if (!visited[i]) {
			visited[i] = 1;
			two.push_back(arr[i]);
			sol(arr, n + 1, i + 1);
			two.pop_back();
			//cout << "n: " << n  << " arr[idx]: " << arr[idx] << '\n';
			visited[i] = 0;
		}
	}
}

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

	int T;
	cin >> T;
	for (int t = 0; t < T; t++) {
		sum = 0;
		int n;
		cin >> n;
		vector<int> arr;
		for (int i = 0; i < n; i++) {
			int idx;
			cin >> idx;
			arr.push_back(idx);
		}

		sol(arr, 0, 0);
		cout << sum << '\n';
	}
}

---

유클리드 호제법

저번에 친구 과제를 도와주다가 최대공약수를 구하는 함수가 특이한 것을 봤다.

저렇게 해서 구해지나 싶어서 기록은 해두었었다.

int gcd(int n, int m) { // 최대공약수
	if (n % m == 0) {
		return m;
	}

	return gcd(m, n % m);
}

이러한 방법을 유클리드 호제법이라고 한다.

(+개념 참고 https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95)

 

간단하게 설명하면 유클리드 호제법이란

a라는 수와 b라는 수가 있을 때 (단, a > b)

a를 b로 나누었을 때 나머지가 없다면 (b는 a의 약수) b 그 자체로 최대공약수가 된다.

하지만, 나머지 r이 존재한다면 a와 b의 최대공약수는 b와 r의 최대공약수가 된다.

예를 들어 8과 6이 있다면 나머지 2가 존재한다.

6과 2의 최대공약수는 2가 된다.

계산으로 8과 6의 최대공약수를 구해도 2가 되므로 저 공식이 맞다는 것을 확인할 수 있다.

---

소스 코드

솔루션: 백트래킹으로 쌍들을 구해 최대공약수(유클리드 호제법)를 구하고, 이를 총합 변수에다가 더해준다.

위에서는 a가 b보다 커야 한다고 하지만 소스 코드에서는 별다른 swap을 하지 않는다.

왜냐하면 6이 a, 8이 b로 주어졌을 때, 6을 8로 나눈 나머지는 6이 되어 의도치 않게 swap이 되기 때문이다.

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

bool visited[101] = { 0, };
vector<ll> two; // 두 수 고른 거 담을 배열
ll sum; // gcd 총합 구할 변수

ll gcd(ll n, ll m) { // 최대공약수
	if (n % m == 0) {
		return m;
	}

	return gcd(m, n % m);
}

void sol(vector<ll>& arr, int n, int idx) { // 백트래킹
	if (n == 2) {
		ll a = two[0], b = two[1];
		//cout << n << ' ' << m << ' ' << gcd(n, m) << '\n';
		sum += gcd(a, b);
		return;
	}

	for (int i = idx; i < arr.size(); i++) {
		if (!visited[i]) {
			visited[i] = 1;
			two.push_back(arr[i]);
			sol(arr, n + 1, i + 1);
			two.pop_back();
			//cout << "n: " << n  << " arr[idx]: " << arr[idx] << '\n';
			visited[i] = 0;
		}
	}
}

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

	int T;
	cin >> T;
	for (int t = 0; t < T; t++) {
		sum = 0;
		int n;
		cin >> n;
		vector<ll> arr;
		for (int i = 0; i < n; i++) {
			ll idx;
			cin >> idx;
			arr.push_back(idx);
		}

		sol(arr, 0, 0);
		cout << sum << '\n';
	}
}