[C++]GCD 합 - 백준9613

문제

• GCD 합(백준9613)

풀이

문제 해석을 하자면,

• GCD(=최대공약수) 합을 구하는 프로그램

풀이

• 이전에 구한 방식으로 최대공약수를 구한다.(최대공약수와 최소공배수 게시글 참고)
  • 참고로 풀다가 햇갈렸었는데, 최대공약수 1은 당연히 다들 가지고 있다(여기 조건 범위 안에선)
  • 따라서 calTemp 변수가 곱해지기 위해서 1로 설정한것도 맞지만 최대공약수 1로 초기화 한 의미도 있다는 걸 다시 기억.
• 모든 쌍을 접근하기 위해 2중 for문으로 접근하겠다.

코드

#pragma warning(disable:4996)
#include <iostream>
#include <string>
using namespace std;

int inputArr[105];

long long calTemp, calResult, maxNum;

int T, N, i, j, k;

void gcd(int, int);

int main() {
	int t = 0;
	cin >> T;
	for (t = 0; t < T; t++) {
		cin >> N;

		// init
		calResult = 0;
		for (i = 0; i < N; i++) {
			inputArr[i] = 0;
		}

		// input
		for (i = 0; i < N; i++) cin >> inputArr[i];

		// GCD
		for (i = 0; i < N-1; i++) {
			for (j = i + 1; j < N; j++) {
				gcd(inputArr[i], inputArr[j]);
			}
		}

		// output
		cout << calResult << '\n';
	}

	return 0;
}

void gcd(int num1, int num2) {
	// run
	calTemp = 1; // 곱하기를 위함이기도 하지만, 최대공약수 1은 무조건 있으니까 이값으로 초기화
	maxNum = max(num1, num2);

	// 1) 동일할 경우(동일할때는 그냥 최대공약수, 최소공배수 전부 동일한 그 수가 답)
	if (num1 == num2) { 
		calResult += num1;
	}
	// 2) 동일한 경우가 아닐땐
	else {
		for (k = 2; k < maxNum; k++) {
			if (num1 % k == 0 && num2 % k == 0) {
				num1 /= k; num2 /= k;
				calTemp *= k;

				// init
				k = 1;  maxNum = max(num1, num2);
			}
		}
		calResult += calTemp;
	}
}

느낀점

생략