[백준/C++]#9613 - GCD 합

풀이

#include <iostream>
using namespace std;

int gcd(int x, int y) {		// 유클리드 호제법을 사용한 최대공약수 함수 
	int r;
	for (int i=1; i<=min(x,y); i++) {
		if (x%i==0 && y%i==0)	r = i;	
	}
	return r;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, sum = 0;		// sum 함수는 while문 반복마다 초기화
		cin >> n;
		int a[n];
		for (int i=0; i<n; i++) {
			cin >> a[i];
		}
		for (int i=0; i<n-1; i++) {
			for (int j=i+1; j<n; j++)
				sum +=gcd(a[i],a[j]);
		}
		cout << sum << '\n';
	}
	return 0;
}

개념

이전에 풀었던 최대공약수를 구하는 문제에서 파생된 문제이다.

최대공약수 자체의 계산은, 저번에 구현한 함수 gcd(x, y)를 사용한다.

각 테스트 케이스마다 주어진 값들간의 최대공약수를 모두 구해야한다.

첫번째 테스트케이스의 예시

다음과 같은 방식으로 모든 가능한 짝을 계산하기로 생각했다.

이러한 계산을 위해서 이중 for문을 사용해야한다.

---

풀이 

풀이는 매우 간단하다.

 

1. 이중 for문을 사용해 가능한 짝의 경우를 나타낸다.

 

2. i와 j 인수를 통해 gcd 함수에 배열 값을 넣는다.

 

3. 이 값을 sum을 통해 받아서 테스트 케이스 안에서 출력한다.

 

---

+a

몇가지 신경써야할 부분이 있었다.

 

for문을 사용한 최대공약수 함수를 사용하면, 시간초과가 발생한다.

이중 for문안에서 함수를 사용해, 1부터 min(x,y)까지 반복하는 for문이 한번 더 들어가면 너무 계산이 많아지는 것 같다.

이 문제는 유클리드 호제법을 사용한 순환함수로 해결했다.

 

sum을 int 자료형으로 정의하면 '틀렸습니다'가 나타난다.

수많은 반복을 하면서 결과값인 sum은 int 자료형 범위를 넘어서는 것 같다.

 

※생각해보니, 배열 a에 n을 대입해서 정의했는데 왜 컴파일에 문제가 발생하지 않았다.

배열에 동적인 변수를 지정하기 위해 C++ CTL vector가 필요한 것으로 알고있는데, 아주 의문이다.

일단 n이 1~100의 아주 작은 값이라서 큰 문제가 발생하지 않았다고 추측된다..

향후 공부해서 이유를 추가할 생각이다.