[C++][BAEKJOON] 9613번 GCD합

문제

9613번: GCD 합

 

풀이

유클리드 호제법을 이용하여 주어진 숫자에 모든 경우의 수에 따라 최대공약수를 구하는 문제.

 

고민했던 부분은 3가지였다.

 

1. 최대공약수를 구할 두 수를 선택(조합을 이용해서)하는 방법

2. 선택한 두 수를 저장 및 최대공약수 연산 함수에 보내는 방법

3. 항상 큰수를 작은 수로 나누게 숫자를 배치하는 방법

 

무식하게 일단 구현해보자!는 맘으로 덤볐더니 반복문과 벡터를 좀 많이 썼다... (상세 설명은 주석 참조...)

인터넷을 찾아보니 너무도 간단하게 구현할 수 있었다... 근데 두 수를 선택하는 방법을...ㅠ 그리고 작은수를 큰수로 나눠도 되는구나....? 왜그런지.... 아시는 분은 댓글 plz ㅠ -> 해결완료(맨아래 첨부)

 

코드1 (매우 무식)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void SelectTwoNum(vector<int> num_vector);//최대공약수를 구하기위해 두 수를 선택하는 함수
int CalculateGCD(int a, int b);//나머지를 구해서 최대공약수를 구할 함수

//내림차순을 위한 조건문 함수
bool lower(int a, int b) {
	return (a > b);
}

int main() {
	int test_case = 0, num_count = 0, num = 0;//테스트 케이스 수, 한 줄당 입력받는 수, 한 줄에 입력되는 숫자들(벡터에 넣으려구)
	vector<int> num_vector;//한 줄에 입력된 숫자들을 담은 벡터

	cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		cin >> num_count;
		for (int j = 0; j < num_count; j++) {
			cin >> num;
			num_vector.push_back(num);
		}
		if (num_count >= 2) {//한 줄에 입력된 수가 2 이상이면 최대공약수를 구하러 감. 1개 이면 그 수가 곧 최대공약수.
			sort(num_vector.begin(), num_vector.end(), lower);//항상 큰수를 작은 수로 나누게 내림차순으로 정렬함. 
			SelectTwoNum(num_vector);//경우의 수를 구해야 해서 2개의 숫자를 뽑으러 가자.
			num_vector.clear();//숫자를 다시 받아야 하므로 num_vector 초기화
		}
		else cout << num_vector.front() << "\n";
	}
	return 0;
}

void SelectTwoNum(vector<int> num_vector) {
	vector<int> check_vector;//0과 1을 이용해서 2수를 뽑는 경우의 수를 찾기 위한 벡터
	vector<int> selected_num;//선택된 두 수를 담은 벡터
	long long sum = 0;

	for (int i = 0; i < 2; i++) { check_vector.push_back(1); }//1을 2개 넣어주고(선택될 인덱스 표시)
	for (int i = 0; i < num_vector.size() - 2; i++) { check_vector.push_back(0); }//나머지는 0으로.(선택 안될 인덱스 표시)
	sort(check_vector.begin(), check_vector.end());//작은 수부터 순열을 구해야 하므로 오름차순 정렬. 중간에 비는 경우 없이 모든 경우의 수를 구하기 위해.

	do {
		for (int i = 0; i < num_vector.size(); i++) {
			if (check_vector[i]){//선택된 인덱스면 selected_num에 추가해줌.
				selected_num.push_back(num_vector[i]);
				if (selected_num.size() > 1) {//선택된 수가 2개면 최대공약수 구하러 떠나기.
					sum += CalculateGCD(selected_num.front(), selected_num.back());//구한 합들을 저장
					selected_num.clear();//숫자를 다시 선택해야 하므로 selected_num벡터 clear.
					break;
				}
			}
		}
	} while (next_permutation(check_vector.begin(), check_vector.end()));//다음 2수를 뽑는 경우의 수가 있는지 확인. 있으면 반복문 계속 진행.
	cout << sum << "\n";
}

int CalculateGCD(int a, int b) {//최대 공약수
	if (a%b == 0) {
		return b;
	}
	return CalculateGCD(b, a%b);//유클리드 호제법 GCD(a, b) = GCD(b, a%b)임을 이용
}

코드2(참된 정답)

#include <iostream>
#include <vector>
using namespace std;

int CalculateGCD(int a, int b);

int main() {
	int test_case, num_count, num;
	cin >> test_case;

	while (test_case--) {
		vector<int> num_vector;

		cin >> num_count;
		for (int i = 0; i < num_count; i++) {
			cin >> num;
			num_vector.push_back(num);
		}
		long long sum = 0;

		for (int i = 0; i < num_count; i++) {
			for (int j = i+1; j < num_count; j++) {
				sum += CalculateGCD(num_vector[i], num_vector[j]);
			}
		}
		cout << sum << "\n";
		num_vector.clear();
	}
	return 0;
}

int CalculateGCD(int a, int b) {
	if (a%b == 0) {//왜 작은수를 큰수로 나눠도 괜찮은걸까...
		return b;
	}
	return CalculateGCD(b, a%b);
}

 

알고리즘 문제를 너무 오랜만에 풀었더니 감이 다 죽어따... 다시 끌어올리자 ! I believe in me!

---

2022.04.02 오후 업데이트

 

두번째 풀이의 CalculateGCD함수에서 a%b 를 할 때, a>b의 조건을 확인하는 부분이 없어서 만약 a<b의 경우, 왜 작은수를 큰수로 나눠도 괜찮은걸까... 라는 생각을 했었는데, 어차피 나누어지지 않는 값이라 그대로 a가 나오기 때문에 자리를 바꿔서 한번 더 실행하게 되므로 괜찮은거 였다.

 

예를 들어, GCD(4, 8)의 경우 GCD(a,b) == GCD(b, a%b)이므로 GCD(8, 4%8)가 될텐데 4는 8로 나누어지지 않으므로 몫이 0이고 나머지가 4가 된다. 그리고 GCD(8, 4) 이 값이 다시 나오므로 GCD(4, 0)이 되어 최대공약수 4를 도출할 수 있는 것이었따~!!!

 

공학수학2까지 했는데, 수학 다까먹엇죠~? 화이띵이다ㅎㅎ...