[백준 9417번] 최대 GCD (C++)

문제링크 : https://www.acmicpc.net/problem/9417

9417번: 최대 GCD

 

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

int n, result;
string s, s_num;
vector<int>arr;

int gcd(int a, int b)  //최대공약수 구하기
{
	if (b == 0) return a;
	else return gcd(b, a % b);
}

int main()
{
	fastio;
	cin >> n;
	cin.ignore();  //개행문자 지우기

	while(n--)
	{
		arr.clear(); s_num = ""; result = -1; // 매번 초기화
		getline(cin, s);                      //문자열 입력받기
		for (int i = 0; i < s.length(); i++)
		{
			if (s[i] != ' ')  //문자라면 더해줌
			{
				s_num += s[i];
			}
			else              //공백이라면 더한걸 정수로 바꿔서 푸쉬
			{
				arr.push_back(stoi(s_num));
				s_num = "";   //푸쉬했으므로 초기화
			}
		}
		arr.push_back(stoi(s_num));  //마지막으로 더해진 값 푸쉬

		for (int i = 0; i < arr.size() - 1; i++)           //맨 마지막 값은 비교할 필요 없음
		{
			for (int j = i + 1; j < arr.size(); j++)
			{
				result = max(result, gcd(arr[i], arr[j])); //최대공약수 중 가장 큰 값 저장
			}
		}
		cout << result << "\n";
	}
	
	return 0;
}

 

이번 문제는 입력을 문자열로 받는다.

처음에 테스트케이스 수에대한 값을 입력받을 때, 개행문자가 같이 넘어오므로 cin.ignore을 통해서 지워준다.

 

이후 받은 문자열에 대해서 문자열의 각 문자에 대해 문자면 더해주고, 공백일 경우 더해줘서 만들어진 문자열을 정수로 바꿔서 벡터에 담아준다.

 

이때 공백일때만 푸쉬해주므로 마지막으로 더해져서 만들어진 문자열은 반복문이 끝나고 따로 푸쉬를 해줘야만 담아진다.

 

이후 이중 for문으로 완전탐색을 하여 가장 큰 최대공약수를 가져온다.

(최대공약수는 재귀방법을 통해 구하였다)