백준 9613. GCD 합

알고리즘 기초 문제 중 수학1 연습 문제

백준 9613. GCD 합

1. 간단 설명

---

양의 정수 N이 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 문제

각 테스트케이스마다

수의 개수 n과, n개의 수가 주어지는데

이 n개의 수의 가능한 모든 쌍의 GCD의 합을 구하는 문제

예시

예를들어

1
4 10 20 30 40

이 주어진 경우

TC1 은 4개의 수 {10, 20, 30, 40}이 주어진다

이 수들로 만들 수 있는 GCD는

10, 20 => 10 10, 30 => 10 10, 40 => 10 20, 30 => 10 20, 40 => 20 30, 40 => 10

이므로 합은 70이 된다

2. 문제 분석

---

주의사항

• 테스트 케이스 개수가 최대 100개이고, 각 테케에서 수의 개수는 100개다
• 입력으로 주어지는 수들은 1,000,000을 넘지 않는다. 최대 999,999!

필요 변수들

• 테스트 케이스 개수 int T (1<= t <=100)
• 수의 개수 int n (1 < n ≤ 100)
• 주어지는 수들을 저장할 벡터. vector<int> v 각 수는 100만을 넘지 않으므로 int형 가능
• gcd의 합들을 저장할 변수 long long int res
  • TC 100 999999 999999 ... 999999 의 gcd의 합은 100c2 * 999999이므로,
    약 49억이므로 INT형은 Overflow 발생
• 조합을 위한 변수들
  • algorithm 헤더의 next_permutation을 사용해도 되지만 직접 구현해봄
  • 선택된 배열 원소를 저장할 int arr[MAX]
  • 이미 선택된 배열 체크를 위한 bool check[MAX]

알고리즘

1. TC입력 받기
2. 각 TC별 다음 수행
	2-1. 기존에 사용했던 res와 벡터 초기화
	2-2. n과 n개의 원소 입력받기
	2-3. n개의 원소 중, 2개를 조합
		2-3-1. 조합을 이용해 두개의 원소를 선택
		2-3-2. 2개의 원소가 선택됬다면, 두 수의 GCD를 구해 res에 더한다
	2-4. 최종 결과값 res를 출력

3. 소스코드

---

#include <iostream>
#include <vector>
#include <numeric>

#define MAX 101

using namespace std;

int n;
long long int res = 0;
vector<int> v;
int arr[MAX];
bool check[MAX];

void combination(int level, int start) {
	if (level == 2) {
		// 고른 두개의 수의 gcd를 res에 더한다
		res += gcd(arr[0], arr[1]);
		return;
	}
	for (int i = start; i < n; i++) {
		if (check[i] == true) continue;
		check[i] = true;

		arr[level] = v[i];
		combination(level + 1, i);

		check[i] = false;
	}
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	int T; cin >> T;
	while (T--) {
		res = 0;
		v.clear();

		cin >> n;
		for (int i = 0; i < n; i++) {
			int tmp; cin >> tmp;
			v.push_back(tmp);
		}

		// 2개 조합
		combination(0, 0);

		cout << res << '\n';
	}

	return 0;
}

배운점

첫 제출에서 오버플로우 생각 안하고 제출했다가 한번 틀렸다

제출하기 전에 꼭 최대값 TC 생각해보고 제출할 것!