[PS] 백준 #9417. 최대 GCD

문제 정보

• 난이도: 실버 IV
• 문제 주소: https://www.acmicpc.net/problem/9417
• 이 문제를 푼 이유: 그룹 연습 Div.2

 

문제

정수 M개가 주어졌을 때, 모든 두 수의 쌍 중에서 가장 큰 최대공약수 찾는 프로그램을 작성하시오.

 

나의 풀이

이 문제는 보자마자 브루트포스로 모든 쌍에 대해서 유클리드 호제법을 적용하여 최대 공약수를 구한 뒤 그 중 최대값을 구하면 되겠다고 생각했다. (최대 정수의 개수가 100이므로 4500쌍이 최대기 때문에 모든 경우의 수를 구해도 된다.) 하지만 이 문제에서 예상치 못하게 시간을 많이 낭비했는데, 그 이유는 입력받는 형태 때문이였다. 

3
10 20 30 40
7 5 12
125 15 25

위와 같이 입력값의 개수가 주어지지 않고 개행문자를 입력하기 전까지 무작위로 숫자들을 입력받아야 했다. 처음에는 string으로 입력받아 형변환해주면 되겠지하고 코드를 짰다. 그랬더니 아무리해봐도 공백 처리가 안되어 답답했는데, 해답은 getline 함수에 있었다. 입출력 관련 함수들은 주기적으로 복습을 해줘야 미래에 시간낭비를 막을 수 있을 것 같다...

#include <bits/stdc++.h>

using namespace std;

int GCD(int a, int b) {
	if (b == 0) return a;
	return GCD(b, a % b);
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n; 
	cin >> n;
	string s; getline(cin, s);

	while (n--) {
		string str;
		getline(cin, str);
		vector<int> vec, changeNum;
		for (int i = 0; i < str.size(); i++) {
			if (str[i] != ' ') {
				changeNum.push_back(str[i] - '0');
			}
			else {
				int num = 0;
				for (int j = 0; j < changeNum.size(); j++) {
					num += changeNum[j] * pow(10, changeNum.size() - j - 1);
				}
				vec.push_back(num);
				changeNum.clear();
			}
		}

		int num = 0;
		for (int j = 0; j < changeNum.size(); j++) {
			num += changeNum[j] * pow(10, changeNum.size() - j - 1);
		}
		vec.push_back(num);
		changeNum.clear();


		// 모든 경우의 최대공약수 중 최대 구하기
		int result = 1;

		for (int i = 0; i < vec.size(); i++) {
			for (int j = i; j < vec.size(); j++) {
				if (i != j)
					result = max(result, GCD(vec[i], vec[j]));
			}
		}
		cout << result << "\n";
	}
}