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

9417번: 최대 GCD

---

문제 )

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

 

 

 

입력 :

첫째 줄에 테스트 케이스의 개수 N (1 < N < 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 양의 정수 M (1 < M < 100)개가 주어진다. 모든 수는 -231보다 크거나 같고, 231 -1보다 작거나 같다. 

 

 

 

출력 :

각 테스트 케이스마다, 입력으로 주어진 수의 모든 두 수의 쌍의 최대공약수 중 가장 큰 값을 출력한다.

 

 

 

 

풀이)

C++이 익숙하지 않다보니 한 줄로 입력된 문자열을 나누어 vector에 저장하는 것부터 상당히 헤매었다.

 

여러가지 방법 중 sstream을 이용한 방법이 가장 간단하다고 생각되었고,

 

이를 이용한 방법을 통해, 문자열을 입력받아, 최대공약수를 구해주었다. 

 

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
 
// 최대공약수 구하기
int gcd(int a, int b) {
    int temp;
 
    // a가 b보다 작을 경우에만.
    if (a < b) {
        temp = a;
        a = b;
        b = temp;
    }
 
    // 최대공약수 구하기.
    while(a % b != 0) {
        temp = a;
        a = b;
        b = temp % b;
    }
 
    return b;
}
 
 
int main() {
 
    int n;
    cin >> n;
    // \n을 없애주기 위해.
    cin.ignore();
 
    for(int i = 0; i < n; i++) { 
        vector<int> v;     
        string line;
        string num;  
        getline(cin, line);
        // 문자열 쪼개 입력 받기
        stringstream sstream(line);
        while(getline(sstream, num, ' ')) {
            v.push_back(stoi(num));
        }
        
        int temp = 0;
        int maxGCD = 0;
        for(int j = 0; j < v.size() - 1; j++) {
            for(int k = j + 1; k < v.size(); k++){
                temp = gcd(v[j], v[k]);
                // 삼항 연산자.
                maxGCD = maxGCD < temp ? temp : maxGCD;
            }
        }
        cout << maxGCD << endl;
    }
 
    return 0;
}

 

---

출처 : https://www.acmicpc.net/problem/9417

9417번: 최대 GCD