#9613: GCD 합

백준 9613번: GCD 합

문제:

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

입력:

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

풀이:

• 이 문제는 유클리드 호제법을 이용하여 푸는 문제법이다. #2609: 최대공약수와 최소공배수에 자세한 설명이 나와 있으니 유클리드 호제법이 무엇인지 모른다면 한번 읽어보길 바란다.
• 우선 모든 입력값을 알맞게 배열에 저장한 뒤 모든 쌍의 경우를 계산하기 위한 2중 for문을 만들어줘야 된다. 두번째 for문의 시작은 항상 첫번째 for문의 값보다 1 크게 설정해주면 모든 값을 확인 할 수 있다. 그 다음에 각각 값을 자료형에 저장 해준 뒤 큰 수가 항상 같은 자료형에 오도록 if문에서 만들어준다. 그 이후에는 유클리드 호제법을 적용해 준다. 그렇게 구한 정답을 출력하고 다음에 계산하는 값들에 또 더해지지 않게 0으로 초기화 해주면 된다.

⚠️ 이 문제를 풀 때 주의 해야 할 점은 gcd의 합(우리가 구하려는 정답 값)이 최대 100,000,000이기 때문에 int 자료형에 담기지 않기 때문에 overflow가 발생한다. 따라서, long long을 사용해준다.

🔍 앞으로 문제를 풀 때는 이 문제에서 나올 수 있는 최대 크기의 답이 무엇인가 고려하고 푸는 습관을 들이면 한번에 깔끔하게 문제를 풀 수 있을 것이다.

코드:

#include <iostream>

using namespace std;

int main(){
	//최대 값이 100*1,000,000이기 때문에 long long을 써야 됨 
	long long gcd = 0; 
	int n, m;
	//입력 
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> m;
		//m 크기 배열에 저장 
		int numbers[m];
		for(int j = 0; j < m; j++){
			cin >> numbers[j];
		}
		//모든 쌍의 경우를 위한 2중 for문 
		for(int j = 0; j < m; j++){
			for(int k = j+1; k < m; k++){
				//계산을 위한 숫자값 저장 
				int temp, a = numbers[j], b = numbers[k];
				//큰 수를 a에 놓기 위한 if문 
				if(a < b){
					temp = a;
					a = b;
					b = temp;
				}
				//유클리드 호제법 
				while(a%b){
					temp = b;
					b = a%b;
					a = temp;
				}
				gcd += b;
			}
		}
		//출력 
		cout << gcd <<'\n'; 
		//정답 값 초기화
		gcd = 0;
	}
}