[알고리즘 문제 풀기] 최대 GCD(9417)

1. 문제 풀이 아이디어

• 최대공약수를 구하는 함수를 구현하여 문제를 해결할 수 있다.

2. 나의 정답 코드

StreamReader reader = new StreamReader(Console.OpenStandardInput());
StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());

int n = int.Parse(reader.ReadLine());
for (int i = 0; i < n; i++)
{
    int[] arr = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
    int result = 0;
    for (int j = 0; j < arr.Length - 1; j++)
    {
        for (int k = j + 1; k < arr.Length; k++)
        {
            result = Math.Max(result, gcd(arr[j], arr[k]));
        }
    }
    writer.WriteLine(result);
}

writer.Close();
reader.Close();
int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    return gcd(b, a % b);
}

3. 정리

• 최대공약수를 구하는 함수 gcd를 구현한다.

• Array.ConvertAll을 사용하여 문자열 배열에서 정수 배열로 바꾸어 arr에 저장한다.

• 2가지 숫자를 뽑는 모든 경우의 수에서 최대공약수의 최대값을 구해 문제를 해결한다.