ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 9613 GCD 합 (C++)

Posted on Feb 5, 2021 #수학   #유클리드 호제법   #Algorithm  

9613 | GCD 합

🙋‍♀️ 문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

🙌 입출력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

🙋‍♂️ 예제 입출력

3
4 10 20 30 40
3 7 5 12
3 125 15 25

70
3
35

🚀 코드

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

int getGcd(int a, int b) {
	int tmp = 0;
	if (a < b) { // 대소 비교를 통해 항상 큰수가 a가 되도록 함
		tmp = a;
		a = b;
		b = tmp;
	}

	while (b != 0) {
		tmp = a % b;
		a = b;
		b = tmp;
	}
	return a;
}

int main() {
	int t, n;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		vector<int> v;
		int x = 0;
		for (int j = 0; j < n; j++) {
			cin >> x;
			v.push_back(x);
		}
		long long sum = 0;
		for (int k = 0; k < n; k++) {
			for (int l = k + 1; l < n; l++) {
				sum += getGcd(v[k], v[l]);
			}
		}
		cout << sum << '\n';
	}
	return 0;
}

🌠 메모

이 문제를 풀기 위해 주의해야 할 두 가지 포인트가 있다.

  • 유클리드 호제법을 이용한 최대공약수 구하기
  • 입력으로 주어지는 수가 1,000,000을 넘지 않는다.

유클리드 호제법에 대해서는 다른 포스팅에서 다루도록 하겠다.

최대공약수를 구하는 방법은 여러가지가 있겠지만, 간단하고 빠른 방법이기 때문에 유클리드 호제법을 사용하는게 바람직하다.

이후 가능한 모든 쌍의 합을 구하기 위해 k, l for문을 사용했고 어렵지 않게 코드를 짤 수 있었지만, 정답이 아니었다.

우연의 일치인지는 모르겠지만 최근에 푼 문제는 모두 변수의 자료형 범위를 넘어가서 틀렸었다. 이 문제 또한 입력으로 들어오는 수가 1,000,000이하이므로 gcd를 구하다보면 int의 범위를 넘어가므로 sum은 long이나 long long으로 선언하는게 맞다.

문제를 제대로 읽지 않고 생각없이 코딩을 하다 발생하는 문제이니, 다음부터는 sum이나 rst의 자료형은 무조건 long으로 선언하도록 해야겠다…



# 카테고리