[백준9613] 가능한 최대공약수 쌍의 합 구하기 (C++)

BOJ 바로가기

#include <iostream>
using namespace std;
int gcd(int, int);
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	while (n--) {
		int m, arr[100] = { 0 };
		long long sum = 0;
		cin >> m;
		for(int i=0;i<m;i++) {
			cin >> arr[i];
		}
		for (int i = 0; i < m - 1; i++) {
			for (int j = i + 1; j < m; j++) {
				sum += gcd(arr[i], arr[j]);
			}
		}
		cout << sum<<'\n';
	}
	return 0;
}
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}

잘 풀었다고 생각했는데 틀려서 당황스러웠는데 이번에도 자료형 때문이었다.

sum이 int 자료형이 커버 가능한 범위를 초과하는 경우가 있기 때문에 sum을 long long 자료형으로 설정해주면 오류가 나지 않는다.

문제를 푸는 데 핵심이 되는 아래 코드를 기억해두면 좋을 것 같다.

재귀함수를 이용하여 최대공약수 구하기

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}