[백준9613] 가능한 최대공약수 쌍의 합 구하기 (C++)
#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);
}
}
Author And Source
이 문제에 관하여([백준9613] 가능한 최대공약수 쌍의 합 구하기 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoohoo030/백준9613-가능한-최대공약수-쌍의-합-구하기-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)