[알고리즘 문제 풀기] 링(3036)

1. 문제 풀이 아이디어

• 최대공약수를 구한 후, 각각의 분수를 약분하여 출력한다.

2. 나의 정답 코드

StreamReader sr = new(Console.OpenStandardInput());
StreamWriter sw = new(Console.OpenStandardOutput());
int n = int.Parse(sr.ReadLine());
string[] split = sr.ReadLine().Split();
int a = int.Parse(split[0]);
for (int i = 1; i < n; i++)
{
    int r = int.Parse(split[i]);
    int g = gcd(a, r);
    Console.WriteLine($"{a / g}/{r / g}");
}


sw.WriteLine();
sr.Close();
sw.Close();

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

3. 정리

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

• 첫 번째 입력을 a에 저장하고, 이후 각 입력값을 r로 받아 최대공약수를 구한다.

• a와 r을 최대공약수로 나눈 값을 출력하여 분수를 약분한 결과를 보여준다.